선교사와 식인종(Cannibals and Missionaries)

(사진 출처 : http://www.plastelina.net/games/game2.html 링크를 타고 실제로 게임을 해 볼 수 있다.)

 정원이 2명인 배로 선교사 3명과 식인종 3명이 강을 건너가야한다. 그런데 문제는... 식인종 수가 선교사 수보다 많으면 선교사가 잡아먹힌다. 어떻게하면 모두 무사히 강을 건널 수 있을까?

풀이

 강건너기문제에서 답을 찾기 쉬운 방법은 '중간점 찾기'라고 생각한다.

 이것이 무슨 이야기인고하니, 왼쪽에서 오른쪽으로 가는 것과 오른쪽에서 왼쪽으로 가는 것이 대칭적이기 때문에 사람들이 배를 타고 움직이는 방법 역시 대칭적으로 나올 것이라고 생각하는 것이다. 그럴 경우 필연적으로 대칭 포인트가 중간이 있을 것이므로 첫 상태에서 중간점까지만 생각하면 남은 부분은 대칭적으로 움직이게하면 된다는 것이다.

 이해를 위해 이 문제를 가지고 설명하면,

선교사,식인종|        (선교사,식인종)       |선교사,식인종

이렇게 사람들이 위치할 때 좌로 보나 우로 보나 똑같으므로 대칭의 중간이라고 볼 수 있는 것이다.

 실제로 해답은 다음과 같다.

(선교사 : M , 식인종 : C)

                |            (    )|CCCMMM

                |            (CC)|CMMM

                |(CC)            |CMMM

C              |(C  )            |CMMM

C              |            (C  )|CMMM

C              |            (CC)|MMM

C              |(CC)            |MMM

CC            |(C  )            |MMM

CC            |            (C  )|MMM

CC            |            (MM)|CM

CC            |(MM)            |CM

CM            |(CM)            |CM

CM         |     (CM)    |CM

CM            |            (CM)|CM

CM            |            (MM)|CC

CM            |(MM)            |CC

MMM         |(C  )            |CC

MMM         |            (C  )|CC

MMM         |            (CC)|C

MMM         |(CC)            |C

MMMC      |(C  )             |C

MMMC      |             (C  )|C

MMMC      |             (CC)|

MMMC      |(CC)             |

MMMCCC |(    )              |