|
| |
|
|
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.
|
|
0
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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
|
|
|
|
STATUS
|
approved
|
| |
|
|
