짝을 짓는 것과 한 바퀴 도는 것은 왜 다른 문제일까요?

같은 허용 이동에서 두 점씩 덮는 구성과 모든 점을 한 번 도는 구성은 연결성 요구가 다름을 보여요.

나뭇결이 보이는 목재 블록이 줄지어 놓인 골목 바닥

사진: Jim Roberts · CC BY-SA 4.0 · 원본 출처

정수 x,y가 각각 1,2,3,4인 열여섯 점이 있어요. 한 번의 이동은 거리 정확히 2인 두 점 사이에서만 허용해요. 모든 점을 두 개씩 짝짓기는 가능할까요? 각 점을 정확히 한 번 방문하고 출발점으로 돌아오는 하나의 닫힌 경로도 가능할까요?

(Δx,Δy)∈{(2,0),(−2,0),(0,2),(0,−2)}.(\Delta x,\Delta y)\in\{(2,0),(-2,0),(0,2),(0,-2)\}.

각 행에서 열1과3, 열2와4를 짝지으면 여덟 쌍이 돼요. 모든 점을 한 번씩 쓰고 각 거리는 2이므로 첫 질문은 가능해요.

반면 한 경로를 따라 이동하는 동안 x의 홀짝과 y의 홀짝이 각각 유지돼요. 점들은 홀홀·홀짝·짝홀·짝짝의 네 묶음으로 나뉘고 각 묶음은 네 점이에요. 어느 점에서 출발해도 다른 묶음의 점을 방문할 수 없어요.

각 묶음 안에서는 정사각형의 네 꼭짓점을 도는 작은 닫힌 경로를 만들 수 있어요. 하지만 네 개의 작은 경로를 발견했다는 사실은 하나의 큰 경로가 있다는 증명이 아니에요. 허용 규칙에는 묶음을 연결하는 이동이 없어요.

같은 점 그림에 짝짓기 선과 방문 경로를 따로 그려 봐요. 모든 점이 한 번씩 사용되었다는 조건은 같아 보이지만, 방문 경로에는 앞 이동과 다음 이동이 이어져야 한다는 추가 구조가 있어요. 풀이에서 그 연결 조건이 사용되었는지 확인해 봐요.

착안 원문: NZMO 2025 Round 2, Problem 1. 위 조건·문항과 해설은 새로 구성했어요. 원문의 문항이나 그림을 번역·재사용한 것이 아니에요.

이 글 공유하기

개인정보 및 방문 통계 안내