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:
1. M1 and C1 cross the river, M1 comes back.
2. C2 and C3 cross the river, C2 comes back.
3. M1 and M2 cross the river, M1 and C1 come back.
4. M1 and M3 cross the river, C3 comes back.
5. C1 and C2 cross the river, C1 comes back.
6. C1 and C3 cross the river.
Now everyone is on the other side.