River Crossing Problems

Farmer, Fox, Goat and Corn

I know of three river crossing problems.  They all involve being able to move people or objects across a river subject to certain constraints.  All three problems are also symmetric in a similar  way.

Consider the simplest of the three problems.  A farmer wants to move a goat, fox and bag of corn across a river.  For the sake of clarity, suppose that the farmer and company start on the left side of the river and end up on the right side. The fox cannot be left alone with the goat because it will eat the goat.  The goat cannot be left alone with the bag of corn because it will eat the corn.  The farmer has a boat that can only hold him and one of the other objects.  How does he get all three across the river?

Try to solve this on your own before looking at the solution below.  Write down the solution, indicating what gets moved across the river and in what direction.






Solution:
Farmer & Goat =>
 <= Farmer
Farmer & Fox =>
<= Farmer & Goat
Farmer & Corn =>
<= Farmer
Farmer & Goat =>



So how does this problem relate to symmetry?  First of all, notice the symmetry between the original and final positions.  The problem starts with the farmer and three objects on one side of the river and ends up will all of them on the other side of the river.

Farmer, Fox, Goat, Corn  (River)   =>  (River) Farmer, Fox, Goat, Corn

The other thing to noice, which not quite so obvious, is that every move is reversible.  Imagine taking a video of the river crossings from the initial position on the left side of the river to the final position on the right side of the river.  If the video is played in reverse, the result is a legal sequence that moves everyone from the right side of the river to the left.  This right to left sequence can be adapted to become another left to right solution to the problem.  This gives a solution symmetry.  Reversing the order and adapting from r(right to left) to (left to right) preserves the property of being a solution to the problem.

It would appear that there are two solutions to the problem, one that starts out by moving the goat and then the fox and another that starts out by moving the goat and then the corn.  In fact there is really only one solution.  Even though the fox is on the top and corn is on the bottom of the local food chain, as far as the problem is concerned they are equivalent.  They both must satisfy the constraint that neither can be left alone with the goat.  What gets eaten by what if this constraint is violated is irrelevant to the solution to the problem.  The fox and corn could be replaced by two foxes or by two bags of corn and the problem would be equivalent.  It therefore follows that in the problem as stated, any solution is symmetric to one which swaps the fox and corn.

Suppose now that we wanted to use our knowledge of symmetries and equivalence of fox and corn to solve the problem. We might start solving the problem as follows:

M1: Farmer & Goat =>
M2:  <= Farmer
M3: Farmer & Fox =>

The position at this point is:
P: Corn (River) Farmer, Fox, Goat

We know of course that we can reverse these moves to get everyone back on the left side. The thing to notice at this point is that if the farmer and the goat cross the river,
 <= Farmer & Goat
we end up with a symmetric position (taking into consideration the corn/goat symmetry):
P': Farmer, Corn, Goat (River) Fox

Since we knew how to transform the previous position to one with everyone on the left side, we can now transform the current position to one with everyone on the right side.  We apply the above sequence of moves in reverse motion.  There is another motion reversal, since we are starting from the opposite side of the river.  The net result is that the moves at  are done in reverse order in the exact same direction as the moves preceding the last one, swapping fox and corn, so we get as the solution:

M1: Farmer & Goat =>
M2:  <= Farmer
M3: Farmer & Fox =>

M4: <= Farmer & Goat

M3': Farmer & Corn=>
M2': <= Farmer
M1': Farmer & Goat =>

Missionaries and Cannibals
Try to use your knowledge of symmetry to solve this river crossing problem.  The statement of this problem may seem politically incorrect. Since this is a well known recreational math problem, I have chosen to use the original language rather than reword it.

Three missionaries and three cannibals want to cross a river.  The boat can only hold two people and there can never be a situation where there are both cannibals and missionaries together on one side of the river with the number of cannibals exceeding the number of missionaries.

This problem is different from the previous one, but like the other there is point of symmetry allowing for a repetition of moves in reverse order.


Japanese River Crossing Problem

Here is a link to animated version of what is apparently a fairly recent river crossing problem that originated in Japan.
Japanese river crossing problem

 You will notice that the problem has "gender symmetry."   That is, any solution will yield another solution if the father and mother are swapped and the sons and daughters are swapped.  Try to solve this on your own before reading my hint.  The problem is a little more difficult than the other two.

Hint: There is a point in the problem where the father and sons are on one side of the river and the mother and daughters are on the other side. Given the gender equivalence this suggests that it should be possible to take advantage of symmetry by moving the cop and robber to the other side.  However, at this point the boat is on the wrong side of the river for transporting the cop and robber.  After a few more moves, the position is the same except that the boat is on the side with the cop and robber, making possible a single move that creates a situation symmetric to the prior move. In the first problem the moves were done in reverse order with swapping for corn/ fox.  In this case, they are done in reverse order with Mother/Father and Daugher/Son swapping.


Back






Home