Missionaries and cannibals problem
From Wikipedia, the free encyclopedia
The missionaries and cannibals problem, and the closely related jealous husbands problem, are classic river-crossing problems.[1] The missionaries and cannibals problem is a well-known toy problem in artificial intelligence, where it was used by Saul Amarel as an example of problem representation.[2][3]
Contents |
[edit] The problem
In the missionaries and cannibals problem, three missionaries and three cannibals must cross a river using a boat which can carry at most two people, under the constraint that, for both banks, if there are missionaries present on the bank, they cannot be outnumbered by cannibals (if they were, the cannibals would eat the missionaries.) The boat cannot cross the river by itself with no people on board.[1]
In the jealous husbands problem, the missionaries and cannibals become three married couples, with the constraint that no woman can be in the presence of another man unless her husband is also present. Under this constraint, there cannot be both women and men present on a bank with women outnumbering men, since if there were, some woman would be husbandless. Therefore, upon changing women to cannibals and men to missionaries, any solution to the jealous husbands problem will also become a solution to the missionaries and cannibals problem.[1]
[edit] Solution
The earliest solution known to the jealous husbands problem, using 11 one-way trips, is as follows. The married couples are represented as A (male) and a (female), B and b, and C and c.[4], p. 291.
| Trip number | Starting bank | Travel | Ending bank |
|---|---|---|---|
| (start) | Aa Bb Cc | ||
| 1 | Bb Cc | Aa → | |
| 2 | Bb Cc | ← A | a |
| 3 | A B C | bc → | a |
| 4 | A B C | ← a | b c |
| 5 | Aa | BC → | b c |
| 6 | Aa | ← Bb | Cc |
| 7 | a b | AB → | Cc |
| 8 | a b | ← c | A B C |
| 9 | b | a c → | A B C |
| 10 | b | ← B | Aa Cc |
| 11 | Bb → | Aa Cc | |
| (finish) | Aa Bb Cc |
This is a shortest solution to the problem, but is not the only shortest solution.[4], p. 291.
As mentioned previously, this solution to the jealous husbands problem will become a solution to the missionaries and cannibals problem upon replacing men by missionaries and women by cannibals. In this case we may neglect the individual identities of the missionaries and cannibals. The solution just given is still shortest, and is one of four shortest solutions.[5]
[edit] Variations
An obvious generalization is to vary the number of jealous couples (or missionaries and cannibals), the capacity of the boat, or both. If the boat holds 2 people, then 2 couples require 5 trips; with 4 or more couples, the problem has no solution.[6] If the boat can hold 3 people, then up to 5 couples can cross; if the boat can hold 4 people, any number of couples can cross.[4], p. 300.
If an island is added in the middle of the river, than any number of couples can cross using a two-person boat. If crossings from bank to bank are not allowed, then 8n−6 one-way trips are required to ferry n couples across the river;[1], p. 76 if they are allowed, then 4n+1 trips are required if n exceeds 4, although a minimal solution requires only 16 trips if n equals 4.[1], p. 79. If the jealous couples are replaced by missionaries and cannibals, the number of trips required does not change if crossings from bank to bank are not allowed; if they are however the number of trips decreases to 4n−1, assuming that n is at least 3.[1], p. 81.
[edit] History
The first known appearance of the jealous husbands problem is in the medieval text Propositiones ad Acuendos Juvenes, usually attributed to Alcuin (died 804.) In Alcuin's formulation the couples are brothers and sisters, but the constraint is still the same—no woman can be in the company of another man unless her brother is present.[1], p. 74. From the 13th to the 15th century, the problem became known throughout Northern Europe, with the couples now being husbands and wives.[4], pp. 291–293. The problem was later put in the form of masters and valets; the formulation with missionaries and cannibals did not appear until the end of the 19th century.[1], p. 81 Varying the number of couples and the size of the boat was considered at the beginning of the 16th century.[4], p. 296. Cadet de Fontenay considered placing an island in the middle of the river in 1879; this variant of the problem, with a two-person boat, was completely solved by Ian Pressman and David Singmaster in 1989.[1]
[edit] See also
[edit] References
- ^ a b c d e f g h i "The Jealous Husbands" and "The Missionaries and Cannibals", Ian Pressman and David Singmaster, The Mathematical Gazette, 73, #464 (June 1989), pp. 73–81.
- ^ On representations of problems of reasoning about actions, Saul Amarel, pp. 131–171, Machine Intelligence 3, edited by Donald Michie, Amsterdam, London, New York: Elsevier/North-Holland, 1968.
- ^ p. 9, Searching in a Maze, in Search of Knowledge: Issues in Early Artificial Intelligence, Roberto Cordeschi, pp. 1–23, Reasoning, Action and Interaction in AI Theories and Systems: essays dedicated to Luigia Carlucci Aiello, edited by Oliviero Stock and Marco Schaerf, Lecture Notes in Computer Science #4155, Berlin/Heidelberg: Springer, 2006, ISBN 978-3-540-37901-0.
- ^ a b c d e Jealous Husbands Crossing the River: A Problem from Alcuin to Tartaglia, Raffaella Franci, pp. 289–306, From China to Paris: 2000 Years Transmission of Mathematical Ideas, edited by Yvonne Dold-Samplonius, Joseph W. Dauben, Menso Folkerts, and Benno van Dalen, Stuttgart: Franz Steiner Verlag, 2002, ISBN 3515082239.
- ^ Cannibals and missionaries, Ruby Lim, pp. 135–142, Conference proceedings: APL '92, the International Conference on APL, 6-10 July 1992, St. Petersburg, Russia, edited by Lynne C. Shaw, et al., New York: Association for Computing Machinery, 1992, ISBN 0-89791-477-5.
- ^ Tricky Crossings, Ivars Peterson, Science News, 164, #24 (December 13, 2003); accessed on line February 7, 2008.
