두 그룹을 번갈아 모두 방문하면, 출발점으로 돌아올 수 있을까요?

두 점과 세 점으로 나눈 두 그룹에서, 서로 다른 그룹의 점끼리만 연결해요. 모든 점을 한 번씩 방문하는 길은 있어도 출발점으로 돌아오는 순환은 만들 수 없는 이유를, 두 그룹의 점 개수로 확인해요.

나무 체스판 위 양쪽에 놓인 밝고 어두운 체스 말

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

왼쪽에A,B 두점, 오른쪽에1,2,3 세점이있어요. 서로다른그룹의두점은모두변으로연결하고같은그룹끼리는연결하지않는다. 전체는연결되어있어요. 모든점을한번씩방문하는닫힌순환이가능할까요? 출발점으로돌아오지않는경로도비교하라.

E={A1,A2,A3,B1,B2,B3}.E=\{A1,A2,A3,B1,B2,B3\}.

오른쪽에서한번이동하면왼쪽, 다시이동하면오른쪽이에요. 닫힌순환에서는출발점으로돌아오는마지막변도그룹을바꾼다. 따라서순환에사용된두그룹의점수는같아야해요.

문항의전체점수는2와3이어서조건을어긴다. 그러나끝점이서로다른방문경로는직접쓸수있어요.

1→A→2→B→3.1\to A\to2\to B\to3.

이경로는모든점을한번씩방문해요. 마지막3에서첫1로닫으려면같은그룹끼리의변이필요하지만그변은없다. 마지막을B로바꾸어억지로닫으면B를재방문하므로원래조건을잃는다.

교사는“모든점에서다른점으로갈수있다”는연결성설명을인정하면서도그것이한순환에모든점을한번씩담는다는결론까지주지는않는다고분리해요. 한관문을지워끊어지는앞글과달리이그래프는어느점하나를지워도남은연결이유지되지만그룹수불균형이닫힘을막는다.

착안 원문: Camins d’Hamilton. 문항의 좌표·조건·논증은 새로 구성했어요. 원문 도판이나 활동 지시의 번역이 아니에요.

이 글 공유하기

개인정보 및 방문 통계 안내