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