정수 x,y가 각각 1,2,3,4인 열여섯 점이 있다. 한 번의 이동은 거리 정확히 2인 두 점 사이에서만 허용한다. 모든 점을 두 개씩 짝짓기는 가능한가? 각 점을 정확히 한 번 방문하고 출발점으로 돌아오는 하나의 닫힌 경로도 가능한가?
각 행에서 열1과3, 열2와4를 짝지으면 여덟 쌍이 된다. 모든 점을 한 번씩 쓰고 각 거리는 2이므로 첫 질문은 가능하다.
반면 한 경로를 따라 이동하는 동안 x의 홀짝과 y의 홀짝이 각각 유지된다. 점들은 홀홀·홀짝·짝홀·짝짝의 네 묶음으로 나뉘고 각 묶음은 네 점이다. 어느 점에서 출발해도 다른 묶음의 점을 방문할 수 없다.
각 묶음 안에서는 정사각형의 네 꼭짓점을 도는 작은 닫힌 경로를 만들 수 있다. 하지만 네 개의 작은 경로를 발견했다는 사실은 하나의 큰 경로가 있다는 증명이 아니다. 허용 규칙에는 묶음을 연결하는 이동이 없다.
수업에서는 같은 점 그림에 짝짓기 선과 방문 경로를 따로 그린다. 모든 점이 한 번씩 사용되었다는 조건은 같아 보이지만, 방문 경로에는 앞 이동과 다음 이동이 이어져야 한다는 추가 구조가 있다. 풀이에서 그 연결 조건이 사용되었는지 확인하게 한다.
착안 원문: NZMO 2025 Round 2, Problem 1. 위 조건·문항과 해설은 새로 구성했다. 원문의 문항이나 그림을 번역·재사용한 것이 아니다.