Three missionaries and three cannibals want to get to the other side of a river. There is a small boat, which can fit only two. To prevent a tragedy, there can never be more cannibals than missionaries together.
How can all the cannibals and missionaries cross the river safely ?
Answer
Let M = Missionary and C = Cannibal.
This is how they cross the river:
- M,C →
- ← M
- C,C →
- ← C
- M,M →
- ← M,C
- M,M →
Now, there are 3 missionaries and 1 cannibal on the other side of the river. This cannibal can fetch the other 2 cannibals one by one.