River crossing puzzle

Dog, sheep, and cabbage

A river crossing puzzle is a type of puzzle in which the object is to carry items from one river bank to another, usually in the fewest trips. The difficulty of the puzzle may arise from restrictions on which or how many items can be transported at the same time, or which or how many items may be safely left together. ^[1] The setting may vary cosmetically, for example, by replacing the river by a bridge. ^[1] The earliest known river-crossing problems occur in the manuscript Propositiones ad Acuendos Juvenes (English: Problems to sharpen the young), traditionally said to be written by Alcuin. The earliest copies of this manuscript date from the 9th century; it contains three river-crossing problems, including the fox, goose, and bag of beans puzzle and the jealous husbands problem. ^[2]

The wolf, goat and cabbage problem

The bridge and torch problem

Solutions to some puzzles charted as timelines

Well-known river-crossing puzzles include:

• The fox, goose, and bag of beans puzzle, in which a farmer must transport a fox, goose and bag of beans from one side of a river to another using a boat which can only hold one item in addition to the farmer, subject to the constraints that the fox cannot be left alone with the goose, and the goose cannot be left alone with the beans. Equivalent puzzles have also been stated involving a fox, chicken, and bag of grain, or a wolf, goat, and cabbage, etc.
• The jealous husbands problem, in which three married couples must cross a river using a boat which can hold at most two people, subject to the constraint that no woman can be in the presence of another man unless her husband is also present. This is similar to the missionaries and cannibals problem, in which three missionaries and three cannibals must cross the river, with the constraint that at any time when both missionaries and cannibals are standing on either bank, the cannibals on that bank may not outnumber the missionaries.
• The bridge and torch problem.
• Propositio de viro et muliere ponderantibus plaustrum. In this problem, also occurring in Propositiones ad Acuendos Juvenes , a man and a woman of equal weight, together with two children, each of half their weight, wish to cross a river using a boat which can only carry the weight of one adult. ^[3]

These problems may be analyzed using graph-theoretic methods, ^{[4] [5]} by dynamic programming, ^[6] or by integer programming. ^[3]

Graph theoretic formulation

Let ${\displaystyle G=(V,E)}$ be an undirected graph whose vertex set ${\displaystyle V}$ represents items that the farmer must carry, and whose edge set ${\displaystyle E}$ consists of pairs of items that conflict. For example, if a vertex ${\displaystyle v_{1}}$ represents a goose and ${\displaystyle v_{2}}$ the bag of beans, then the two vertices would be connected since the goose cannot be left on the same side of the river with a bag of beans. Note that the edges are undirected, as the nature of the conflict between the two items does not affect the fact that they cannot be left on the same side of the river. The object of the problem is to determine the minimum size of the boat such that a trip is feasible; this is known as the Alcuin number of ${\displaystyle G}$.

Consider a successful river crossing in which the farmer first carries a subset ${\displaystyle V'}$ of items across the river, leaving the remaining ${\displaystyle V\setminus V'}$ items on the shore. Because the trip is successful, there must be no conflicts in the items left onshore; ie. in ${\displaystyle G}$, there are no edges in ${\displaystyle E}$ between any two elements of ${\displaystyle V\setminus V'}$. This implies that all edges ${\displaystyle E}$ have one or both vertices in ${\displaystyle V'}$, ie. that ${\displaystyle V'}$ is a vertex cover of ${\displaystyle G}$. Therefore, the size of the boat must be at least as large as the size ${\displaystyle \tau (G)}$ of the minimum vertex cover of ${\displaystyle G}$; this forms a lower bound on the Alcuin number of ${\displaystyle G}$: ${\displaystyle Alcuin(G)\geq \tau (G)}$.

On the other hand, it is possible to complete a successful trip with boat size equal to ${\displaystyle \tau (G)+1}$. This can be achieved by requiring the members ${\displaystyle V'}$ of a minimum vertex cover to remain on the boat at all times; these items number ${\displaystyle \tau (G)}$, and thus leave one more space on the boat. Because there are no conflicts among any of the remaining ${\displaystyle V\setminus V'}$ items, they can be taken across the river one at a time in any order, occupying the one remaining space on the boat. Thus, ${\displaystyle Alcuin(G)\leq \tau (G)+1}$, forming an upper bound for ${\displaystyle Alcuin(G)}$. Combining these together, we have ${\displaystyle \tau (G)\leq Alcuin(G)\leq \tau (G)+1}$, ie. either ${\displaystyle Alcuin(G)=\tau (G)}$ or ${\displaystyle Alcuin(G)=\tau (G)+1}$. ^[7]

Csorba, Hurkens, and Woeginger proved in 2008 that determining which of ${\displaystyle Alcuin(G)=\tau (G)}$ or ${\displaystyle Alcuin(G)=\tau (G)+1}$ holds is NP-hard. ^[5] Because the minimum vertex cover problem is NP-complete, it follows that computing the Alcuin number of a graph ${\displaystyle G}$ is NP-hard. However, for certain classes of graphs, stronger results hold. For example, for planar graphs, determining which of the two relations holds can be done in polynomial time (though determining either ${\displaystyle Alcuin(G)}$ or ${\displaystyle \tau (G)}$ remains NP-hard); for bipartite graphs, ${\displaystyle Alcuin(G)}$ and ${\displaystyle \tau (G)}$ can both be computed exactly in polynomial time. ^[5]

See also

• Vertex cover

References

1. Peterson, Ivars (2003), "Tricky crossings", Science News, 164 (24), retrieved 2008-02-07.
2. p. 74, Pressman, Ian; Singmaster, David (1989), ""The Jealous Husbands" and "The Missionaries and Cannibals"", The Mathematical Gazette, 73 (464), The Mathematical Association: 73–81, doi:10.2307/3619658, JSTOR   3619658 .
3. Borndörfer, Ralf; Grötschel, Martin; Löbel, Andreas (1995), Alcuin's Transportation Problems and Integer Programming, Preprint SC-95-27, Konrad-Zuse-Zentrum für Informationstechnik Berlin, archived from the original on 2011-07-19.
4. Schwartz, Benjamin L. (1961), "An analytic method for the "difficult crossing" puzzles", Mathematics Magazine, 34 (4): 187–193, doi:10.2307/2687980, JSTOR   2687980 .
5. Csorba, Péter; Hurkens, Cor A. J.; Woeginger, Gerhard J. (2008), "The Alcuin number of a graph", Algorithms: ESA 2008, Lecture Notes in Computer Science, vol. 5193, Springer-Verlag, pp. 320–331, doi:10.1007/978-3-540-87744-8_27 .
6. Bellman, Richard (1962), "Dynamic programming and "difficult crossing" puzzles", Mathematics Magazine, 35 (1), Mathematical Association of America: 27–29, doi:10.2307/2689096, JSTOR   2689096 .
7. Numberphile (2018-01-05). River Crossings (and Alcuin Numbers) - Numberphile . Retrieved 2024-05-17– via YouTube.

External links

• YouTube video