Variations on the Missionaries and Cannibals Problem
By George Spahn and Doron Zeilberger
.pdf
.tex
appeared in
Discrete Mathematics Letters, v. 11 (2023),84-90.
Written: Oct. 19, 2022
ל כ ב ו ד
נ ח ו ם
צ ב י
ב ן
י צ ח ק
ה ל ו י
נ ר ו
י א י ר
ב מ ל א ת
ל ו
פ ה
ש נ י ם
Dedicated to our academic father (for DZ) and grandfather (for GS),
Harry Dym (b. Jan 26, 1938), on his forthcoming eighty-fifth birthday.
We explore both automated and human approaches to generalizations of this famous puzzle.
We got the idea for this project when one of us (DZ) found in a used bookstore a book written by Clive Dym,
(Harry Dym's brother), where the Missionaries and Cannibals problems is used to illustrate Engineering Design.
Maple packages
-
Cannibals.txt,
a Maple package to solve and investigate Cannibals and Missionaries river-crossing puzzles
-
DiGpaths.txt,
a Maple package to solve any puzzle that can be described in terms of paths in a directed graph,
for general graphs. It includes most of the stuff that can be done with Cannibals.txt and much more.
-
RiverCrossing.txt,
a Maple package to solve any river-crossing puzzle using symbolic computations,
and very efficiently finding the number of solutions.
Sample Input and Output for Cannibals.txt
-
If you want to see the four solutions to the original puzzle with 3 missionaries, 3 cannibals, boat max. capacity 2, and safety margin (min. of |missionaries|-|cannibals|) 0,
the input gives the
output.
-
If you want to see all the solutions to puzzle with 5 missionaries, 5 cannibals, boat max. capacity 3, and safety margin (min. of |missionaries|-|cannibals|) 0,
the input gives the
output.
-
If you want to see all the solutions to puzzle with 9 missionaries, 9 cannibals, boat max. capacity 4, and safety margin (min. of |missionaries|-|cannibals|) 0,
the input gives the
output.
-
If you want to see all the solutions to puzzle with 8 missionaries, 3 cannibals, boat max. capacity 2, and safety margin (min. of |missionaries|-|cannibals|) 1,
the input gives the
output.
-
If you want to see all the solutions to puzzle with 10 missionaries, 3 cannibals, boat max. capacity 3, and safety margin (min. of |missionaries|-|cannibals|) 2,
the input gives the
output.
Sample Input and Output for DiGpaths.txt
-
If you want to see the number of solutions, and a representative solution for various cases
the input gives the
output.
-
If you want to see intersting integer sequences arising from counting the number of solutions
the input gives the
output.
Sample Input and Output for RiverCrossing.txt
-
If you want to see all the solutions, using computer algebra to the Cabbage/Sheep/Wolf problem, the original
3 Missionaries and 3 Cannibals problem, and the version with 4 Missionaries and 4 Cannibals and Boat Size 3 then
the input gives the
output.
-
If you want to see an article with 139 explicit conjectured generating functions (that we are SURE are correct, and we know how to prove them if we had to), for
sequenes enumerating the number of solutions to infinite families of generalized Missionaries and
Cannibals problems
the input gives the
output.
Doron Zeilberger's Home Page