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.