|
| |
|
|
A300576
|
|
Number of nights required in the worst case to find the princess in a castle with n rooms arranged in a line (Castle and princess puzzle).
|
|
4
|
|
|
|
1, 2, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100, 102, 104, 106, 108, 110, 112, 114, 116, 118, 120, 122
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
This is a logic puzzle. There is a castle with n rooms arranged in a line. The princess living in the castle sleeps in a different room each night, but always one adjacent to the one in which she slept on the previous night. She is free to choose any room in which to sleep on the first night. A prince would like to find the princess, but she will not tell him where she is going to sleep each night. Each night the prince can look in a single room. What strategy should he follow in order to guarantee that he finds the princess as quickly as possible?
Christian Perfect (see link) considered the case when the rooms are arranged as a general graph. He showed that the set of solvable graphs is exactly the set of trees not containing the "threesy" subgraph, which is A130131. He also showed that for d-level binary trees with 1 <= d <= 4 the number of required nights is 1, 2, 6, 18. Binary trees with d >= 5 are unsolvable as they contain "threesy".
|
|
|
LINKS
|
|
|
|
FORMULA
|
For n >= 3, a(n) = 2*n - 4.
a(n) = 2*a(n-1) - a(n-2) for n > 4.
G.f.: x*(2*x^3 - x^2 + 1)/(x - 1)^2. (End)
|
|
|
EXAMPLE
|
For n = 1, there is only room to search, so a(1) = 1.
For n = 2, the prince searches room 1 on the first night. If the princess is not there that means she was in room 2. If the prince searches room 1 again then he is guaranteed to see the princess as she has to move from room 2 to room 1 (she cannot stay in the same room). So a(2) = 2.
For n = 3, the prince searches room 2 on the first night. If the princess is not there that means she was either in room 1 or 3. On the second night she must go to room 2 and this is where the prince will find her. So a(3) = 2.
For n = 4, an optimal solution is to search rooms (2,3,3,2), so a(4) = 4.
For n = 5, an optimal solution is to search rooms (2,3,4,4,3,2), so a(5) = 6.
In the general case for n >= 3, an optimal solution is to search rooms (2,3,...,n-1,n-1,...,3,2), so a(n) = 2*n - 4.
|
|
|
MATHEMATICA
|
CoefficientList[ Series[(2x^3 - x^2 + 1)/(x - 1)^2, {x, 0, 62}], x] (* Robert G. Wilson v, Mar 12 2018 *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy,changed
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
