[2월의 퍼즐] 미로 속의 암소

올해는 음력으로 신축년 소띠해이다. 소와 관련된 퍼즐을 한번 다루어 봐도 괜찮을 것 같다.

유명한 교양 수학 저술가이자 수학자인 이언 스튜어트^{Ian Stewart}는 미국의 과학 전문 잡지 <사이언티픽 어메리컨^{Scientific American}>에 ‘수학 레크리에이션^{Mathematical Recreation}‘이라는 칼럼을 연재하고 있다. 이 잡지는 전설적인 작가 마틴 가드너^{Martin Gardner}가 ‘수학적 게임^{Mathematical Games}‘을 연재한 것으로도 유명하다.

이언 스튜어트는 자신의 칼럼에서 “미로 속의 암소^{cows in the maze}“라는 퍼즐을 다룬 적이 있다. 지시문이 적힌 글상자가 여러 개 있고, Yes/No에 따라 이동하여 마지막으로 암소가 있는 상자로 빠져나가면 되는 문제였다. 원작자는 애버트^{Robert Abbott}로 자기 참조 상황을 교묘하게 활용한 일종의 논리 미로 퍼즐이었다.

그의 문제는 너무 어려워서, 여기서는 아주 간단하게 만든 문제를 다루어 보자. 애버트의 문제에 관심이 있는 사람은 “cows in the maze”를 검색해 보거나 이언 스튜어트의 책 『미로 속의 암소』를 찾아보면 되겠다.

먼저 흑백 바둑돌 하나씩을 준비하자. 처음에는 아래 그림의 1번 칸에 검은돌, 3번 칸에 흰돌을 놓고 시작한다. 여기서 1번 칸의 돌을 선택하면, “흰돌이 있는 칸의 번호가 홀수다.”라는 문장은 참이 되므로 1번 칸에 있던 돌을 2번 칸으로 옮긴다. 3번 칸에 있던 돌은 움직이지 않는다.

다음으로 3번 칸의 돌을 선택하면, “검은돌이 있는 칸의 번호가 짝수다.”는 참이 되므로, 3번 칸에 있던 돌을 4번 칸으로 옮긴다. 당연히 2번 칸에 있던 돌은 움직이지 않는다.

이런 식으로 바둑돌이 있는 칸을 선택하여 그 문장의 참거짓에 따라 바둑돌을 계속 이동하다가 어느 한 바둑돌이 가장 아래에 소가 있는 칸에 도착하면 게임이 종료된다. 돌을 교대로 선택할 필요는 없으며, 검은돌을 여러 번 연속해서 선택하거나 흰돌을 여러 번 연속해서 선택할 수 있다.

신중하게 생각하지 않으면 미로 속에서 소를 찾아 헤매게 된다. 어떤 순서로 바둑돌을 선택하면 소를 찾을 수 있을까?