A classic of delicate maneuvers: moving forward does not always mean getting closer to the solution, and each movement has consequences on both sides at the same time.
Missionaries and cannibals
Riddle statement
Three missionaries and three cannibals must cross a river in a boat that only accepts one or two people.
On no shore can there be a group in which the cannibals outnumber the missionaries, unless there are no missionaries on that shore.
Is it possible for them all to cross safely? If yes, in how many minimum journeys?
Show solution
Solution
Answer: Yes. Everyone can cross in 11 paths.
A valid sequence (M = missionary, C = cannibal):
- CC →
- C ←
- CC →
- C ←
- MM →
- MC ←
- MM →
- C ←
- CC →
- C ←
- CC →
The key is to use the cannibals first to move the boat without ever leaving the missionaries in the minority on a shore where there are cannibals. Once the three missionaries can cross safely, the transfer is completed without difficulty.
It is not a question of moving "reasonable pairs", but of keeping the critical condition satisfied on both banks at all times.