Wolf, Goat and Cabbage
______
A farmer has a wolf, a goat and a cabbage. He must cross the river using a boat.
The boat will hold him and one other object: wolf, goat or cabbage. There is an additional complication:
- the wolf will eat the goat;
- the goat will eat the cabbage,
unless the farmer is present.
Can the farmer get the wolf, goat and cabbage to the other side of the river without any mishaps?
· On four pieces of paper write F, W, C, and G to represent the the four main characters: farmer, wolf, cabbage and goat. Make yourself a large version of the diagram below.
· This figure show the `Start' bank and `Finish' bank. Recall the rules of the puzzle
1. You must move all four characters from the one side of the river to the other.
2. The farmer must row the boat (neither the cabbage or the wolf can do this). This mean the farmer must move all objects across the river.
3. The wolf will eat the goat; the goat will eat the cabbage, unless the farmer is present.
Place the four characters on the `Start' side of the river. Can you work out how to move all four characters from one bank to the other so that nothing is eaten? Keep a record of how you solve the puzzle. Is there only one solution? If there is more than one can you find it and record it?
______
the Further Mathematics network
Wolf, Goat and Cabbage
______
It is possible to record and study this puzzle mathematically. We will represent the puzzle as a network diagram. On the picture of the river, you will see that the `Start' bank is labelled 0 and the `Finish' bank is labeled 1. The table below can be used to record the positions of the wolf, goat, cabbage and farmer. When a character is on the `Start' bank enter 0 and then the character is on the `Finish' bank enter a 1.
The start position must always be:
FARMER / WOLF / CABBAGE / GOAT0 / 0 / 0 / 0
The finishing position when you have solved the puzzle must always be
FARMER / WOLF / CABBAGE / GOAT1 / 1 / 1 / 1
For each character there are two possible positions: either 0 or 1.
· How many different positions are there?
· Use the table below to record all the different position that the farmer, wolf, cabbage and goat can be in.
FARMER / WOLF / CABBAGE / GOAT______
the Further Mathematics network
Wolf, Goat and Cabbage
______
Not all the positions you found are needed. For example, we have seen if we initially move the goat from the start side to the finish side then we move
(0,0,0,0) to (1,0,0,1).
If the wolf or cabbage are to be moved then the farmer must return to the start bank; that is, position 0. This means that we cannot move from (1,0,0,1) to (1,1,0,1) without first going through the position (0,0,0,1). This means that we can work out where the farmer must be at each stage of the puzzle but the positions of the wolf, cabbage and goat and the sequence of moves we made to get there.
· In the table below write out only the positions of the wolf, cabbage and goat.
WOLF / CABBAGE / GOAT· The entries of this table represent coordinates. Can you think of any object that has these coordinates as its nodes? Draw this object.
______
the Further Mathematics network
Wolf, Goat and Cabbage
______
Mathematical Solution
At the beginning we have the position (W,C,G)=(0,0,0). The farmer is also in position 0. The edges of the cube represent different moves in the puzzle. For example, there are three moves we can make from the start position:
- take the goat over,
- take the cabbage over,
- take the wolf over.
These are represented graphically by the edges from the node at (0,0,0). A move is called good if nothing eats anything else, a move is called bad if either the wolf eats the goat or the goat eats the cabbage since the farmer leaves them alone together. For example, if we start by taking the wolf across the river, then the farmer must leave the goat with the cabbage, hence this move is bad.
The arrow indicates the direction of the move we make.
The direction we move along an edge is important!
______
the Further Mathematics network
Wolf, Goat and Cabbage
______
The vertices of the cube are all labelled so that the first coordinate is the position of the wolf, the second coordinate is the position of the cabbage and the third is the position of the goat. So for example: (0,1,0) mean wolf in position 0, cabbage in position 1 and goat in position 0.
· Start from the point (0,0,0) where the farmer must be at position 0. Work out whether the three moves you can make to (1,0,0), (0,1,0) and (0,0,1) are good or bad. In each case explain why the move is good or bad and record what the farmer must do to make this move
· Now from the position you are in after a good move, work out whether the moves you can do from the new position are good. In each case it is important to keep track of where the farmer is as this determines whether a move is good or not. (Remember the direction you move along an edge represents a different move.)
· Continue moving along the edges, labeling the edges as good or bad if the represent good or bad moves. Until you arrive at the point (1,1,1). When you arrive at this point you should have a connection between (0,0,0) (the start) and (1,1,1) (the finish) by good edges, which represent good moves. This means we have found all the solutions to this problem.
· Now select only the good edges, which represent the good moves in the puzzle, redraw the network diagram in two dimensions
The Next Day....
The following day the farmer has an even more difficult problem. He now has an additional animal: a dragon. This is a special dragon, it only eats wolves, unless a cabbage is present. The farmer has to cross the river again, getting all the animals to the opposite bank. So we now have the following restrictions:
- the wolf will eat the goat unless the farmer is present,
- the goat will eat the cabbage unless the farmer is present,
- the dragon will eat the wolf unless a cabbage is present.
______
the Further Mathematics network
Wolf, Goat and Cabbage
______
Now we ask the same question as before:
Can the farmer move all his belongings from one side of the river to the other without any mishaps?
For ease of notation write D for dragon. Any position can be represented using four numbers in the form (D,W,G,C). Again we use 0 to denote the starting side of the river, and 1 to denote the side opposite to the start. So, for example, (1,0,1,0) represents the dragon and goat on the opposite side of the river and the wolf and cabbage on this side of the river.
· Using the methods above can you work out the network diagram for this puzzle and its solution? This is not an easy question and you will find it useful to use your river diagram with the farmer and his four belongings.
______