River crossing puzzle

from Wikipedia, the free encyclopedia

River crossing puzzles are a genre of brain teasers that aim to bring a group of defined members across a river with as few crossings as possible, whereby the boat cannot hold the entire group at the same time and certain constellations of group members are prohibited on the banks. The oldest written record of this type of exercise is found in the Propositiones ad acuendos iuvenes from the late 9th century , which contains four such exercises . Among these is the most well-known problem of this type of task, the problem of wolf, goat and cabbage , in which a man has to bring the two animals and the cabbage across the river while only being able to take one of the animals or the cabbage with him and prevent it must that the cabbage or the goat be eaten.

Examples

Wolf, goat and cabbage

The wolf, goat and cabbage problem is the best known example of a river crossing puzzle. A man wants to cross a river with a wolf, a goat and a cabbage, but the boat can only hold one other passenger. He cannot leave the wolf with the goat or the goat with the cabbage unattended on a bank. The task is to develop a plan that complies with these conditions and manages with as few crossings as possible.

To solve this, the man should first cross the river with the goat, leave it on the other bank and return alone. Then he drives the wolf to the other side, leaves it there and returns with the goat. He leaves this on the exit bank, crosses with the cabbage and returns alone. Finally he brings the goat to the target bank a second time, which solves the problem. An alternative solution is to swap the wolf and cabbage in the above order.

The puzzle is common in many cultures, with passengers being adapted to local conditions. The problem has also been passed down with fox, chicken and grain. The puzzle is also widespread in Africa, with cheetahs, chicken and rice, for example. In the Aarne-Thompson-Uther-Index , stories with this motif are listed under ATU 1579, but this riddle is also often used in modern entertainment media.

The jealous husbands

The problem of jealous husbands is also known from the Propositiones : three married couples (in the Propositiones they are sibling pairs) want to cross a river, but the boat only holds two people. Husbands are jealous of each other, so no one will allow their wife to sit on the shore or in a boat with another man when they are not there.

An easier variant of this puzzle emerges if the condition is weakened a little: the women must obviously never be in the majority (unless there are no men with them), otherwise one of them will be with a strange man without her own is there. In this version, the task becomes the problem of missionaries and cannibals with a reformulation of the framework story: three missionaries and three cannibals want to cross a river, but the boat only offers space for two people. In order not to have to fear being eaten up, the missionaries must never be outnumbered by the cannibals.

The bridge

A variation on the type of task can be found in Saul X. Levmore and Elizabeth Early Cook's Problem of Bridge Crossing: Four people, labeled A, B, C and D, want to cross a bridge at night, but they only have one lantern with them. Without the lantern it is impossible to cross the bridge in the dark, but its glow only extends so far that only two people can walk across the bridge at the same time. A takes 5 minutes to cross, B 10, C 20 and D 25 minutes. Since the lantern is no longer burning, they have to find a way to cross the bridge as quickly as possible.

Here the lantern takes on the role of the boat; instead of the number of crossings, its duration should be minimized. In the naive solution, A brings the other three to the other side one after the other, returning to the starting point twice himself. This takes 10 + 5 + 20 + 5 + 25 = 65 minutes. However, there is a quicker solution: A and B cross the bridge, A returns with the lantern. Then C and D cross over together as the two slowest, the lantern brings B back before he and A cross the bridge one more time. This plan only takes 10 + 5 + 25 + 10 + 10 = 60 minutes.

Further examples

In addition to these well-known examples, there are many other river crossing puzzles. So the problem of jealous husbands was posed for a larger number of couples, with the addition of an island in the middle of the river. A systematic study with a complete solution to this problem is by Ian Pressman and David Singmaster .

A small collection of different river crossing puzzles can also be found in the riddle book Amusements in Mathematics by Ernest Dudeney .

Mathematical investigation

From a mathematical point of view, river crossing puzzles fall into the field of combinatorial optimization : the best one should be selected from a larger but finite number of admissible solutions. Graph theory provides a simple model for river crossing problems : a state can be described by specifying the bank on which the individual people and the boat are located. First you delete the states that contradict the conditions, the rest are taken as nodes of a graph . Two nodes are connected by an edge if there is a legal crossing between them. The result is a graph in which the shortest path from the initial state to the final state is sought.

The graph consists of 10 nodes that are connected by edges. At the top is "MWZK", connected to "_W_K" at the bottom, then to "MW_K". From there two paths lead further, one to "___K" and further to "M_ZK", the other via "_W__" to "MWZ_". Both "M_ZK" and "MWZ_" are connected to "__Z_", which is connected to the last node "____" via "M_Z_".
The graph for the wolf, goat and cabbage problem

In the example of the wolf, goat and cabbage, each state can be described by indicating whether the man, the wolf, the goat and the cabbage are on the exit bank or not. Since only the man can drive the boat, the position of the boat does not have to be specified. So there are different states, the starting point is the goal . Six of the 16 states are forbidden: With , and there is a forbidden constellation on the exit bank, for the analogous situations on the other bank the states , and must be excluded. The remaining 10 states can easily be connected by the permitted crossings to the adjacent graph, from which the two solutions mentioned above can be read directly. MWZK_____WZK_WZ___ZKM___M__KMW__

Individual evidence

  1. ↑ Marcia Ascher: A River-Crossing Problem in Cross-Cultural Perspective. In: Mathematics Magazine. Vol. 63, No. 1, 1990. pp. 26-29. ( JSTOR 2691506 )
  2. ↑ * Piret Voolaid: Hundi, kitse ja kapsapea üle jõe viimine. ATU 1579 metamorfoosid. In: Mäetagused. Hüperajakiri Vol. 28, 2005. ( online )
  3. ↑ Saul X. Levmore, Elizabeth Early Cook: Super strategies for puzzles and games. Doubleday and Company , Garden City, New York, 1981. ISBN 0-385-17165-X .
  4. ^ Ian Pressman, David Singmaster: "The Jealous Husbands" and "The Missionaries and Cannibals". In: The Mathematical Gazette. Vol. 73, No. 464, 1989. pp. 73-81. ( JSTOR 3619658 )
  5. ^ Henry Ernest Dudeney: Amusements in Mathematics. 1917. ( Amusements in Mathematics in Project Gutenberg ( currently not available to users from Germany as a rule ) )
  6. ^ * Benjamin L. Schwartz: An Analytic Method for the "Difficult Crossing" Puzzles. In: Mathematics Magazine. Vol. 34, No. 4, 1961. pp. 187-193. ( JSTOR 2687980 )
    • Robert Fraley, Kenneth L. Cooke, Peter Detrick: Graphical Solution of Difficult Crossing Puzzles. In: Mathematics Magazine. Vol. 39, No. 3, 1966. pp. 151-157. ( JSTOR 2689307 )
    • Péter Csorba, Cor AJ Hurkens, Gerhard J. Woeginger: The Alcuin Number of a Graph. In: Algorithms: ESA 2008. Lecture Notes in Computer Science. Vol. 5193, Springer-Verlag, 2008. pp. 320–331. ( doi: 10.1007 / 978-3-540-87744-8_27 )

Web links