A356480 a(n) is the minimal number of river crossings necessary to solve the missionaries and cannibals problem for n missionaries and n cannibals where the boat capacity is the minimum necessary to allow a solution.

1, 5, 11, 9, 11, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99, 101, 103, 105, 107, 109, 111, 113, 115, 117, 119, 121, 123, 125, 127, 129, 131, 133, 135

Offset: 1

Author

Sela Fried, Aug 09 2022

Keywords

• nonn
• easy

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).

Examples

			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).
		

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).

Crossrefs

Cf. A060747, A167484.

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.