The classic river crossing problem.

This one may be the easiest puzzle that will ever be introduced in this blog. Part of the reason it seems so easy is that it has been mentioned everywhere—even La Habitación de Fermat briefly presents it (my previous post talks more about the film). Wikipedia says that the puzzle dates back to at least the 9th century. Even though I’m sure that the solution is out there, I decided to include this problem because no puzzle blog or website would be complete without it.

The main characters in this problem can have many different names. In La Habitación de Fermat, they are el lobo, la oveja, and la col, or the wolf, the sheep, and the cabbage. In another version, they are the fox, the goose, and the grain. Here, I am going to use the ghost, Pac-Man, and the pac-dot (I didn’t know that those were called pac-dots until now), because they are probably easier to draw than the characters in any of the other versions. Imagine drawing a wolf using Paint.

Problem

A game addict is dreaming about trying to cross a river with a ghost, Pac-Man, and a pac-dot. The only means of transportation available is a boat, which can only be rowed by the game addict and has a maximum capacity of two people/characters/entities. If the ghost and Pac-Man are left alone on either side of the river, the ghost will eat Pac-Man. If Pac-Man and the pac-dot are left alone on either side of the river, Pac-Man will eat pac-dot. The game addict’s task is to cross the river with all three of them while keeping everyone intact. How? 

 

Solution

In fact, there are only two ways to cross the river. To compensate for the easiness of the problem, I will not only show those two ways but explain why there cannot be any other solution.

So this is the initial setup—the ghost, Pac-Man, the pac-dot, and the game addict all on one side. Who can cross first? The game addict cannot take the ghost, because then Pac-Man would eat pac-dot. Nor can s/he take the pac-dot; Pac-Man would be eaten. The only entity that the game-addict can cross with is Pac-Man.

Step 1

 

Now, the game addict, the only one in the group with boat-rowing powers, crosses back to where s/he started.

Step 2

 

There are two things the game-addict can do. S/he can either take the ghost or take the pac-dot. Let’s see what happens in each scenario.

(a) Game addict takes the pac-dot.

Step 3 - Scenario (a)

 

So here we are. Now, the only thing that the game-addict can do is take Pac-Man back to the other side. If s/he crosses by himself, Pac-Man will eat the pac-dot. If s/he takes the pac-dot, we would be wasting time by going back to where we were just a while ago.

Step 4 - Scenario (a)

 

Note that the game addict cannot leave Pac-Man and the ghost alone. S/he would have to take someone with him/her, and that would have to be the ghost. We just moved Pac-Man from the other side, so there is no reason to repeat a step by taking it back.

Step 5 - Scenario (a)

 

Now let’s see what would happen if we pick Scenario (b): taking the ghost instead of pac-dot. It might be a good idea to memorize Step 5, because Scenario (b) will lead to the exact same outcome.

(b) Game addict takes the ghost

Step 3 - Scenario (b)

The game addict cannot cross back to the other side alone—the ghost would eat Pac-Man. Taking Pac-Man is the only option here.

Step 4 - Scenario (b)

Again, the game addict can’t cross alone. S/he must take the pac-dot to the other side.

Step 5 - Scenario (b)

 

See? This outcome is exactly the same as what we ended up with in Scenario (a). The game addict could technically take either the ghost or the pac-dot to the other side, but both would mean going back to what we had at some point in the past, and that would be a waste of time. So the most efficient thing to do is for the game addict to cross alone.

Step 6

 One final step. Take Pac-Man and we are done.

Step 7