OFFSET
1,2
COMMENTS
The problem is: n missionaries and n cannibals must cross the river using a boat. The missionaries must not be outnumbered by the cannibals at either river bank, or on the boat, and the boat cannot cross the river by itself.
It turns out that the necessary boat capacity is two people for n=1,2,3; three people for n=4,5; and four people for n > 5.
This problem is a generalization of the classical missionaries and cannibals problem, in which n = 3 and the boat capacity is two people. In this case the minimal number of crossings is a(3) = 11 (see example).
REFERENCES
P. Norvig and S. J. Russell, Artificial Intelligence: A Modern Approach, Third Edition, 2010. Exercise 3.9.
LINKS
R. Fraley, K. L. Cooke, and P. Detrick, Graphical Solution of Difficult Crossing Puzzles, Mathematics Magazine, Vol. 39 (3), pp. 151-157, (1966).
Wikipedia, Missionaries and cannibals problem.
Index entries for linear recurrences with constant coefficients, signature (2,-1).
FORMULA
G.f.: x*(4*x^6 - 4*x^5 + 4*x^4 - 8*x^3 + 2*x^2 + 3*x + 1)/(x-1)^2.
EXAMPLE
Suppose n = 3 and that all the people must cross from the left river side to the right. Let m and c denote the number of missionaries and the number of the cannibals on the left bank of the river at any time. Let b=L if the boat is on the left bank, b=R if the boat is on the right bank. Then (m, c, b) fully captures the condition of the system. A solution of minimal length is then given by (3, 3, L)-->(2, 2, R)-->(3, 2, L)-->(3, 0, R)-->(3, 1, L)-->(1, 1, R)-->(2, 2, L)-->(0, 2, R)-->(0, 3, L)-->(0, 1, R)-->(1, 1, L)-->(0, 0, R).
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Sela Fried, Aug 09 2022
STATUS
approved