Tricky Crossings

Have you heard the one about an itinerant entertainer traveling with a wolf, a goat, and a basket of cabbages?

The showman comes to a river and finds a small boat that holds only himself and one passenger. For obvious reasons, he can't leave the wolf alone with the goat, or the goat with the cabbages. How does he get his cargo safely to the other side?

The showman would need seven trips to ferry the cabbages, goat, and wolf across the river. The showman crosses the river with the goat and leaves the goat on the far shore, then returns alone to the near shore. He brings the wolf to the far shore and brings the goat back to the near shore. He then brings the cabbages to the far shore and returns alone to the near shore. Finally, the showman brings the goat to the far shore.

Another solution interchanges the wolf and the cabbages.

Brainteasers that involve ferrying people and their belongings across a river under trying circumstances have been around for centuries. This particular version dates back to the eighth century and the writings of Alcuin of York (735–804), a poet, educator, cleric, and friend of Charlemagne.

A variant of this puzzle with a different logical structure also features a predator, its prey, and some food. In this case, however, the human can transport two items at one time.

Suppose, for instance, that a herdsman in North Africa must cross a river with a jackal (a predator), a goat (potential prey), and fig leaves (a potential snack for the goat). One solution is to take the jackal and the goat, leave the jackal while returning with the goat, then ferry across the goat and the fig leaves.

An alternative solution would be to carry over the jackal and the fig leaves, then return for the goat. Although it involves the same number of trips, the second solution might be considered more efficient than the first because the herdsman carries the lightest load on each trip.

In the 16th century, a more elaborate edition of the river-crossing problem, proposed by Venetian mathematician Niccolò Fontana Tartaglia (1499–1557), featured three beautiful brides and their young, handsome, and intensely jealous husbands, who come to a river. The small boat that is to take them across holds no more than two people. To avoid any compromising situations, the crossings must be arranged so that no woman is left with a man unless her husband is also present. How many trips does it take to ferry them all across the river–without igniting an angry outburst?

It turns out that 11 trips are required. Five passages are needed for just two couples. With four or more couples, however, it's impossible to accomplish the crossings under the required conditions.

A similar problem involves n couples and a boat that can carry n – 1 people. Under these circumstances, the number of passages from one bank to the other is 11 for n = 3 (as above), nine for n = 4, and seven for n > 4.

A 19th-century version has three missionaries and three cannibals together on one side of a river, with a boat that holds only two people. In this case, the cannibals must never be allowed to outnumber missionaries on either bank. It takes nine trips to get everyone across: a missionary and a cannibal cross; the missionary returns; two cannibals cross; one cannibal returns; two missionaries cross; one missionary and one cannibal return; two missionaries cross; one cannibal returns; and the remaining two cannibals cross.

Here's a variation from a Russian source: Three soldiers have to cross a river without a bridge. Two boys with a boat agree to help the soldiers, but the boat is so small it can support only one soldier or two boys. A soldier and a boy can't be in the boat at the same time for fear of sinking it. Given that none of the soldiers can swim, it would seem that in these circumstances just one soldier could cross the river. Yet all three soldiers eventually end up on the other bank and return the boat to the boys. How do they do it?

It takes 12 crossings: Both boys go to the opposite bank; one of them brings the boat back to the soldiers; a soldier crosses the river; the boat returns with the other boy; both boys cross the river; one boy returns with the boat; the second soldier crosses the river; the second boy returns with the boat; both boys cross the river; one boy returns with the boat; the third soldier crosses the river; and the second boy returns with the boat. The boys continue on their journey and the three soldiers are on the opposite bank.

Now, what happens if, in each of these problems, theres an island in the middle of the river, which can be used as a temporary landing place? In some cases, the island affects neither the total number of trips nor the feasibility of a successful transfer. In other cases, it actually reduces the number of crossings that are necessary.

These puzzles and their many variants represent ways of dressing up relatively straightforward mathematical problems. They invite attempts at solution that range from trial and error to extensive mathematical analysis. You can even try to model a given problem with slips of paper that represent passengers and a boat.

"Story puzzles are expressions of their cultures and so variations will be seen in the characters, the settings, and the way in which the logical problem is framed," Marcia Ascher of Ithaca College in Ithaca, N. Y., noted in a 1990 article in Mathematics Magazine.

Novel variants of the river-crossing problem continue to surface in a variety of forums. In one recent guise, the puzzles involve crossing a rickety bridge at night within a certain time period with just one lantern to light the way. Such puzzles now even play a role in job interviews at places such as Microsoft.

Mathematician David Singmaster has compiled an extensive bibliography of material devoted to recreational mathematics. "Recreational problems act as historical markers, showing the transmission of mathematics (and culture in general) in time and space," he notes. "In particular, they illustrate the fact that most of the more algebraic and arithmetic parts of mathematics have their origins in the Orient, beginning with Babylonia and China and being transmitted through India and the Arabs.

"One must be a little careful with some of these problems, as past cultures were often blatantly sexist or racist," Singmaster warns. "But such problems also show what the culture was like. . . . The river crossing problem of the jealous husbands is quite sexist and transforms into masters and servants, which is classist, then into missionaries and cannibals, which is racist. With such problems, you can offend everybody!"

From the days of ancient Egypt to modern times, it's all done for the sake of turning what appear to be routine mathematical exercises into problems that tickle–even challenge–the mind.

Originally posted: 8/17/96

Updated: 12/13/03