Crossing the River
A farmer is walking back home with a wolf, a goat and some lettuce. As he was on his way a river appears in front of him. Luckily for him, he sees an abandoned boat. Though it turned out the boat was not big enough for all of them. Farmer had to choose either one of the wolf, goat or lettuce in each time he crosses the river.
But there was a catch here: If they are left alone wolf would eat the goat and goat would eat the lettuce. What is farmer’s strategy in order to cross this river? (P.s: It is not possible to swim across the river.)
The Answer
Between these three only wolf and lettuce can be left alone. Then farmer should start the process with carrying the goat to the right side of the river.
Then he should return the left side and picks up either of the wolf or the lettuce. (Let’s assume that he picks the lettuce.) Farmer reaches the right side of the river with the lettuce. Now before he leaves he realizes that lettuce and goat can’t be left alone. So he takes the goat with him to the left side.
Now, lettuce is alone on the right side of the river as farmer, goat and the wolf are all on the left side. At this point farmer should carry the wolf to the right side and leaves it there with the lettuce as lettuce and wolf can be left alone without a problem.
In the end farmer can go back to the left side of the river and takes the goat to the right side. Hence the problem gets solved.
There wouldn’t be a solution for this puzzle if wolf was eating the lettuce. But, in order to understand that we had to check every possible variation. This would have been a waste of time and energy. Thus we haven’t found an actual method for the solution of this puzzle.
River Algorithm
Graph Theory is a relatively new subject of mathematics. In Graph Theory what matters is the placement and the connection; not the shape. In this part of mathematics objects are described with dots and connections with lines. Then wolf, goat and the lettuce can be represented as dots. Only connection between these three is whether they eat one another or not. In the puzzle goat eats lettuce and wolf eats goat. Hence connections (or lines) should be between them.
If dot disappears, then the connections within disappears as well. In the puzzle we can take only one dot at a time. In the first move we choose the goat. This can be shown in graph as follows:
Deleting the goat dot means to delete the lines connected to it. Graph has no line after the first move which is what we want to accomplish and we managed to do it with deleting only 1 dot. This means another thing: In order to solve the puzzle there must be as many spaces as the deleted dots in the boat.
Let me explain this with an example: Assume that we have to take at least n dots away from the graph in order to get rid of all the lines. This means if boat has n empty spaces the puzzle can be solved.
Let’s add a rabbit to this puzzle.
Second River Puzzle
Now farmer has a goat, a wolf, some lettuce and a rabbit. On top of the previous puzzle rabbit eats the lettuce and wolf eats the rabbit.
In the first puzzle we took goat’s dot and saw that there was no line left in the graph. But in the second puzzle none of the four dots is able to extinguish all the lines of the graph.
This is why in order to extinguish all the lines; we must try to remove at least two dots. For instance:
As seen above when we take goat and the rabbit, all the lines inside the graph disappears. Using graphs we found an algorithm and with that algorithm we know that the boat must have at least 2 spaces in order to solve the second puzzle.
One Wonders…
- Solve the second puzzle.
- Let’s add carrot, cat and mice to the second puzzle. Goat, rabbit and mice eats the carrot and cat eats the mice. Try to find how big the boat should be and solve the puzzle for that boat.
M. Serkan Kalaycıoğlu
kmatematikatolyesi.com 