선교사의 강 건너기 문제

 

선교사의 강 건너기 문제

 

세 사람의 선교사와 세 사람의 식인종 사람이 나루에서 만났다. 두 사람만이 탈 수 있는 나룻배가 하나밖에 없다. 그런데 어떤 경우에라도 선교사의 수가 거기에 있는 식인종 사람보다 적어지면 그들에게 선교사는 살해당한다. 어떻게 하면 무사히 건널 수가 있을까

 

해답례

*선교사=M *식인종 사람=C 라고 하면 다음과 같이 건너면 된다.

차례	이쪽	배안에	건너쪽
0	MMM CCC
1	MMMC	CC→	CC
2	MMMCC	←C	C
3	MMM	CC→	CCC
4	MMMC	←C	CC
5	M C	MM→	MM CC
6	M C	←MC	M C
7	CC	MM→	MMM C
8	CCC	←C	MMM
9	C	CC→	MMM CC
10	CC	←C	MMM C
11		CC→	MMM CCC