Three missionaries and three cannibals are on one side of the river, wanting to get across.

Unfortunately, the only boat available can hold a maximum of two people. The missionaries, wanting to stay safe, can never be on a side with more cannibals than missionaries (even for a moment!). The boat cannot travel under its own power, so there must be at least one person on board for it to cross.

How can the missionaries get safely across?

(In reply to Spoiler by Steve Herman)

1) C1, C2 take the boat. C1 gets down at the other side and C2 comes back with the boat. (C1), (C2, C3, M1,M2,M3)
2) C3 also boards the boat with C2 and they cross the river. C3 also gets down and C2 again comes back.(C1, C3),(C2, M1, M2,M3)
3) M1, M2 take the boat. M1 gets down. M2 takes C3 along and comes back.(C1, M1), (M2, C2, M3, C3)
4) M2, M3 take the boat. Both get down at the other end. C1 comes back this time with the boat. By this time all the Missionaries have crossed the river. (M1, M2, M3), (C1, C2, C3)
5) Now C1, C2 cross the river together. C1 gets down at the other end and C2 comes back with the boat. (M1, M2, M3, C1), (C2, C3)
6) C2, C3 cross the river together. Both get down this time at the other end. (M1, M2, M3), (C1, C2, C3)

Posted by Piyush on 2005-05-31 15:48:16