Who is asking: Student
Level: Secondary
Question:
I am a senior at Lake Orion High School. This question is on a quiz that I have in a college level math class but I am confused because it does not seem like a math question to me.
Nine men and two boys, trekking through the jungle, need to cross a river. They have a small inflatable boat and it's easy enough to row it across the river. The boat, however, can hold no more than one man or the two boys. How can they all get across? (Hint. suppose there was only one man and two boys) Does it make math sense and what would the answer be
Hi Barb,
There are at least two ways you can think of this as a math question. One way is described by Penny and another by Claude.
Penny:
I see this as an example of an inductive argument. The problem starts with nine men and two boys on the East side of the river and no one on the West side. I want to go through a few steps and get to the place where there are eight men and two boys on the East side and one man on the West side. My argument is then to repeat these steps nine times and then have no men and two boys on the East side and nine men on the West side. The two boys then cross the river to complete the task.
The problem then reduces to finding the "few steps" referred to above. This is the essence of the hint. How do you start with one man and two boys on the East side, perform a few steps and get to the place where there are two boys on the East side and one man on the West side?
Claude:
It is a math question; in fact it is a graph theory question. You need to write down a graph whose vertices represent how many mens and boys are on either shore of the river, and where is the boat. For instance, <3m,0b,boat|6m,2b> would mean that there are three mens, no boys and the boat on the first shore, and the six other mens and two boys are on the other shore. Two of these vertices are joined by an edge if you can get from one situation to the other with just one crossing.
For instance <3m,0b,boat|6m,2b> --- <2m,0b|7m,2b,boat> means that starting with the situation above, one of the men on the first shore can cross the river on the boat, so that now there are two mens on the first shore, and the other people and the boat are on the other shore.
A longer path such as <3m,0b,boat|6m,2b> --- <2m,0b|7m,2b,boat> --- <2m,1b,boat|7m,1b> --- <1m,1b|8m,1b,boat> --- <1m,2b,boat|8m,0b> --- <1m,0b|8m,2b,boat> corresponds to a sequence of events:
Starting with three mens, no boys and the boat on the first shore, and the others on the other shore,
- one man crosses from the first to the second shore,
- then one boy crosses the other way,
- then another man crosses like the first,
- then the other boy crosses back,
- then the two boys cross again to the second shore.
Thus there are now only one man left on the first shore, while the eight others, the two boys and the boat are on the second shore.
So the question is: Starting at the vertex <9m,2b,boat|0m,0b> corresponding to the initial situation where everybody and the boat are on the first shore, can you make a path that will lead all the way to the vertex <0m,0b|9m,2b,boat> corresponding to the situation where everybody crossed.
(Note: The hint tells you to warm up by considering the situation where there is only one man and two boys; the corresponding graph has very few vertices, so it is easy to write it all down and find the path you want.)