A detachment of 25 soldiers must cross a wide and deep river with no
bridge in sight. They notice two 12-year-old boys playing in a rowboat by the shore. The boat is so tiny, however, that it can only hold two boys or
one soldier. How can the soldiers get across the river and leave the boys
in joint possession of the boat? How many times does the boat pass from
shore to shore in your algorithm?
Answer:
First, the two boys take the boat to the other side, after which one of them returns with the boat. Then a soldier takes the boat to the other side and stays there while the other boy returns the boat. These four trips reduce the problem size—measured by the number of soldiers to be ferried—by 1. Thus, if this fourtrip procedure is repeated the total of 25 times, the problem will be solved after the total of 100 trips. (Of course, for the general instance of n soldiers, 4n trips will need to be made.)
