Monks and Cannibals

Difficulty:
★★☆☆☆

Problem:

Three monks and three cannibals are trying to cross a river. In front of them is a boat that can fit two. The monks are safe as long as there are at least as many monks as cannibals on both sides of the river, but if there are more cannibals than monks on either side of the river, the cannibals will eat the monks. How can they all cross the river while making sure that no monks get eaten?

Solution:

We start with the following setup (C represents cannibals, M represents monks, dashed line is river, and the brackets are the boat).

CCCMMM [   ] -------------------

At this stage, we can't move two monks across the river because then the remaining monk would get eaten. So we can either (a) move one cannibal and one monk across or (b) move two cannibals across. Let's explore both possibilities.

1. Move one cannibal and one monk at the beginning

Now the configuration is as follows.

CCMM ---------------- [   ] CM

Someone needs to bring the boat back to the other side, and it can't be the cannibal because then there would be more cannibals than monks on the left side. So the monk needs to bring back the boat.

CCMMM [   ] --------------- C

Now what? We can't take two monks (the lone monk on the left side would get eaten), or take one monk and one cannibal (the monk would get eaten when he gets to the right side). So the only thing we can do is take two cannibals.

MMM ------------------- [   ] CCC

One of the cannibals needs to bring the boat back.

MMMC [   ] ------------- CC

The only thing we can do now is to send two monks. This would ensure that they won't get eaten when they get to the right side.

MC --------------------- [   ] MMCC

Now the question is who brings the boat back. We can't send a cannibal -- the monk on the left side would get eaten. We can't send a monk -- the remaining monk on the right side would get eaten. The only thing we can do is send one monk and one cannibal bank.

MMCC [   ] ------------------- MC

Now we can send two monks across the river (and this is the only safe option).

CC ------------------ [   ] MMMC

The lone cannibal can bring the boat back.

CCC [   ] ----------------- MMM

The boat then takes two cannibals across:

C ----------------------- [   ] MMMCC

One of the cannibals brings the boat back to the left:

CC [   ] -------------------- MMMC

And finally, the two cannibals cross the river, and we're done.

----------------------- [   ] MMMCCC

Recall that there's an option we haven't explored, which is to move two cannibals as the starting move. We'll explore this option next, but you'll see that the two options are essentially the same.

2. Move two cannibals at the beginning

Now we have this configuration:

CMMM ------------------ [   ] CC

One of the cannibal brings back the boat.

CCMMM [   ] ----------------- C

Notice that we've ended up in the exact same position as the second configuration from the first option. The remaining steps should be the same.