Return to my Puzzle pages
Go to my home page

Cannibals and Missionaries, etc.

© Copyright 2000, Jim Loy

Here are a few classic puzzles.

Puzzle #1: Three cannibals and three missionaries must cross a river. Their boat can only hold two people. If the cannibals outnumber the missionaries, on either side of the river, the missionaries are in trouble (I won't describe the results). Each missionary and each cannibal can row the boat. How can all six get across the river? Try it before looking at the answer, below.

Puzzle #2: A similar puzzle concerns a farmer, a fox, a goose, and a bag of corn. The farmer wants to get all of this stuff across a different river. His boat will only hold himself, and one of the other three items. The fox will eat the goose if the farmer is not present, and the goose will eat the corn if the farmer is not present. How can the farmer transport all three items across the river? Try this too, before looking at the answer, below.

Puzzle #3: This puzzle may not seem similar, at first. But the solution is similar. You are next to the punch bowl, at a party. You happen to have two glasses, one holds five units (cups, cubic centimeters, whatever), and the other holds three units. You must get exactly four units of punch (doctor's orders perhaps), by filling glasses and dumping back into the bowl. How can you do that? The answer is also below. Note: our aim is to have four units in the five unit glass.

Puzzle #4: (see addendum below).

Answer #1 (cannibals and missionaries):

b=boat, M=missionary, C=cannibal.

from	river	to
bMMMCCC
MMCC	>	bMC (or CC)
bMMMCC	<	C
MMM	>	bCCC
bMMMC	<	CC
MC	>	bMMCC
bMMCC	<	MC
CC	>	bMMMC
bCCC	<	MMM
C	>	bMMMCC
bCC	<	MMMC
	>	bMMMCCC

This is not very difficult, as there are not very many possible moves (ignoring backtracking to the previous state) in any given situation. It is safe to have an equal number of missionaries and cannibals on both sides of the river. And it is safe to have all of the missionaries on either side, and any number of cannibals on either side. All other states are illegal: an unequal number of missionaries and cannibals on either side of the river.

Answer #2 (fox + goose + corn):

f=farmer, F=fox, G=goose, C=corn.

from	river	to
f FGC
FC	>	f G
f FC	<	G
F	>	f GC
f FG	<	C
G	>	f FC
f G	<	FC
	>	f FGC

Notice that when the goose and corn are together, and when the fox and goose are together, the farmer is also there.

Answer #3 (punch):

bowl	5 units	transfer	3 units	bowl
>	5
	2	>	3
	2		0	>
	0	>	2
>	5		2
	4	>	3
	4		0	>

The Excellent book Eureka! (Math fun from many angles) by David B. Lewis, has the following method:

bowl	5 units	transfer	3 units	bowl
			3	<
	3	<	0
	3		3	<
	5	<	1
<	0		1
	1	<	0
	1		3	<
	4	<

My method took one fewer steps. Notice that there are shorter solutions, if we are allowed to drink our four units of liquid a little at a time.

All three of these puzzles can be solved using directed graphs. See The Bridges of Königsberg.

Addendum:

Puzzle #4:In the delightful and fairly unusual book, Mathematical Puzzles and Pastimes, Aaron Bakst gives this problem:

We have three unmarked containers of 12-, 7-, and 5-gallon capacities. The 12-gallon container is full. The problem is to pour into the 7-gallon container 6 gallons of liquid only, and leave 6 gallons in the 12-gallon container.

By "unmarked" he means that the containers have no marks by which you can gauge partial amounts of liquid. So, when you pour from one container into another, you pour as much as you can, leaving one empty or the other full.

The author gives this 12-step solution:

He draws arrows showing which container is poured into which container. But we can figure that out from the table without the arrows. Here is my slightly better solution:

That is one step shorter. Each of the columns in these tables represents a "state" of the problem. We can draw a graph with all of these states (which become "nodes" of the graph) in it. All of the above transitions from state to state happen to be reversible; we can go forward or backward. Other transitions are possible, not all of which are reversible. For example, we can go directly from 4,3,5 (state 7 of the first table) to 7,0,5 (state1), but not vice versa.

There is one other state, not in either table, which seems achievable from the zero state, 0,7,5 which can come from 12,0,0 to 5,7,0 to 0,7,5. Other states, like 4,4,4 are not possible (from the above zero state); they have no connection to the rest of the graph. This follows from my comment above, that each move leaves one container either full or empty.

To find my better solution, I drew a graph. To keep it relatively uncluttered, I ignored paths which back-tracked to previously visited nodes. My graph looks pretty much like the tables, but with circles around the three numbers of each state, and with lines between the connected nodes. I made two mistakes, which required a small amount of erasing.

Return to my Puzzle pages
Go to my home page