Problem of the Week
Problem B and Solution
Goats in a Boat?
Problem
Three goats and three bobcats want to cross a river from the south side of the river to the north side of the river.
All they have is a small boat which can carry exactly 1, 2 or 3 animals at a time. The problem is that if the bobcats outnumber the goats on either riverbank or in the boat, then bad things will happen to the goats.
Design a set of trips back and forth across the river so that all the animals end up on the north side together and such that the goats are never with more bobcats on either riverbank or in the boat. The table may help to organize your thinking.
Trip | Animals on South Side | In the Boat | Animals on North Side |
---|---|---|---|
0 | 3G, 3B | 0 | |
1 | —> | ||
2 | <— | ||
3 | —> | ||
4 | <— | ||
5 | —> | ||
6 | <— | ||
Suggestion: Act out this problem with three student bobcats and three student goats.
Solution
The completed table below reveals that the trip can be safely accomplished in 5 crossings, 3 from south to north and 2 return trips north to south. The number of animals on each side are totals after each trip is done.
Trip | Animals on South Side | In the Boat | Animals on North Side |
---|---|---|---|
0 | 3G, 3B | 0 | |
1 | 2G, 2B | 1G, 1B—> | 1G,1B |
2 | 3G, 2B | <—1G | 1B |
3 | 2B | 3G—> | 3G, 1B |
4 | 3B | <—1B | 3G |
5 | 0 | 3B—> | 3G, 3B |
There are many other solutions. Here is another possibility.
Trip | Animals on South Side | In the Boat | Animals on North Side |
---|---|---|---|
0 | 3G, 3B | 0 | |
1 | 3G, 1B | 2B—> | 2B |
2 | 3G, 2B | <—1B | 1B |
3 | 1G, 1B | 2G, 1B—> | 2G, 2B |
4 | 2G, 2B | <—1G, 1B | 1G, 1B |
5 | 1B | 2G, 1B—> | 3G, 2B |
6 | 1G, 1B | <—1G | 2G, 2B |
7 | 0 | 1G, 1B—> | 3G, 3B |