You’ve been sent for scouting a forest nearby your village. You are done with your duty and on your way back home you are bringing a wolf, a goat and some cabbage with you. Wolf would like a piece of goat and goat is looking hostile against the cabbage, but they can’t do anything with your presence. Then you come across with a deep river. Luckily for you, there is a small boat on coast.
The Catch: Boat is so small it allows you to take only either one of wolf, goat or cabbage. Is there any way you can take everything to the other side of the river safely?
Solving Puzzles with Graphs
In the previous article I told you how Euler used a brand new approach to a seemingly insignificant puzzle and how his method became the basis of graph theory. Drawing graphs in certain cases really improve the chances of reaching an answer. Graphs also help us understand why there is not a solution, in case problem has no solution. Graphs are so powerful at times they can even show us what kinds of conditions are needed to solve a problem that has no solution.
In the river problem, let’s use Euler’s methods. You are all on the left side of the river and you have to get across the right side of it. Now assume that left side of the river is assigned as position 1, and right side as position 2.
There are wolf, goat and cabbage. In the puzzle, those three stand on the position 1 which might be shown as a point named 111 (wolf-goat-cabbage on the positions 1-1-1). Ultimate goal of the puzzle is to find a way to get them all to the point 222.
There are eight different positions for the wolf, goat and cabbage: 111, 112, 121, 122, 211, 212, 221 and 222. For instance 112 means wolf is at position 1 (left side of the river), goat is at position 1 (left side of the river) and cabbage is at position 2 (right side of the river).
Drawing the Graph
We assumed that all these 3-digit numbers represent a point. To get from one point to another, we could only change exactly one digit of it, as we are allowed to take exactly one of wolf, goat or cabbage into our boat. Then there are limited ways to go from one point to another. Let’s assume that if you can go from one point to another, then there is a line connecting those two points.
For instance 111 and 112 has a connection as there is exactly one digit that differ those numbers. Although 111 and 212 has no connection as there are more than one digit that differ those numbers.
Finally we found our points and lines and how they could be drawn as a graph. I think Euler would be proud of us.
Our starting point 111 has three options: 112, 121, 211. Our graph looks like following when all relationships between points are shown:
As our ambition is to reach point 222 from the point 111, it is easy to see the ways to the solution in the graph. However we can’t move between points as we’d like to. We can only use paths which satisfy puzzle’s rules: If they are left alone, wolf eats goat and goat eats cabbage.
Solution
The point 111 has three options: 112, 121 and 211. If we select 112 (taking cabbage to the right side) wolf and goat would be alone, so this path is not good for us. The point 211 would mean leaving goat with cabbage which is forbidden as well. Hence there is only one way to select from the point 111: The path to the point 121.
The point 121 has three options: 111, 122 and 221. We can’t go back, so the point 111 is out. We should choose either 122 or 221.
Choosing 122
This would mean that we are taking cabbage to the right side of the river, near the goat. There are again three options: 121, 222 or 112. We can’t go backwards, so the point 121 is out.
222: Choosing this path would give us the answer. But, in order to do that we must leave goat and cabbage alone and go get wolf. Until we are back to the right side of the river, goat would be doing its final chewing. Hence, we can’t choose this path.
112: This is the only real option we can choose.
From 112, there are again three options: 122, 212 and 111. We can’t go backwards, so the points 122 and 111 are out. Path to the point 212 is the only choice.
At the point 212, wolf and cabbage are on the right side of the river and goat is on the left side. Here, we can go to the left side, pick goat with us and reach the point 222. This would give us the solution we were looking for.
Choosing 221
Now go back and choose the path to the point 221. There are again three options from 221: 222, 211 and 121. We can’t choose the point 121 as it would mean going backwards. Going to the point 222 would solve all our problems, but if we try to do that, we would have to leave wolf and goat alone at the position 2. This gives us the option 211.
The point 211 also gives us three options: 111, 221 and 212. Choosing 111 and 221 would mean going backwards. Then we must follow the path to 212. From the point 212, we can directly choose the path to the point 222. And we would again find the solution within the lines of the rules of the puzzle.
Check It Out
Add other animals and vegetables to these three and try to draw the graph. Using the graph, see if you can find a solution to your puzzle.
M. Serkan Kalaycıoğlu
kmatematikatolyesi.com 