Three missionaries and three cannibals must cross a river with a boat which can carry at most two people at a time. However, if on one of the two banks of the river the missionaries get outnumbered by the cannibals, they will get eaten. How can all 6 men cross the river without anybody gets eaten?
Remark: The boat cannot cross the river with no people on board.
Label the missionaries M1, M2, M3 and the cannibals C1, C2, C3. Then:
- M1 and C1 cross the river, M1 comes back.
- C2 and C3 cross the river, C2 comes back.
- M1 and M2 cross the river, M1 and C1 come back.
- M1 and M3 cross the river, C3 comes back.
- C1 and C2 cross the river, C1 comes back.
- C1 and C3 cross the river.
Now everyone is on the other side.