cp's OEIS Frontend

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.

%I A356480 #75 Aug 20 2022 06:25:48
%S A356480 1,5,11,9,11,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,
%T A356480 47,49,51,53,55,57,59,61,63,65,67,69,71,73,75,77,79,81,83,85,87,89,91,
%U A356480 93,95,97,99,101,103,105,107,109,111,113,115,117,119,121,123,125,127,129,131,133,135
%N 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.
%C A356480 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.
%C A356480 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.
%C A356480 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).
%D A356480 P. Norvig and S. J. Russell, Artificial Intelligence: A Modern Approach, Third Edition, 2010. Exercise 3.9.
%H A356480 R. Fraley, K. L. Cooke, and P. Detrick, <a href="https://www.jstor.org/stable/2689307">Graphical Solution of Difficult Crossing Puzzles</a>, Mathematics Magazine, Vol. 39 (3), pp. 151-157, (1966).
%H A356480 Wikipedia, <a href="https://en.wikipedia.org/wiki/Missionaries_and_cannibals_problem">Missionaries and cannibals problem</a>.
%H A356480 <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (2,-1).
%F A356480 G.f.: x*(4*x^6 - 4*x^5 + 4*x^4 - 8*x^3 + 2*x^2 + 3*x + 1)/(x-1)^2.
%e A356480 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).
%Y A356480 Cf. A060747, A167484.
%K A356480 nonn,easy
%O A356480 1,2
%A A356480 _Sela Fried_, Aug 09 2022