A386462 -id:A386462 - cp's OEIS frontend

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

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

Offset: 1

Dmitry Kamenetsky, Mar 09 2018

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 in a minimum number of nights?
The strategy to find the princess guaranteed within a(n) nights takes on average k(n) nights until the princess is found with lim_{n->oo} k(n) = n-1.5. For n>4, strategies with lower average numbers of trials exist; A386462 provides this strategy for n=8. See there for more information. - Ruediger Jehn, Aug 05 2025
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".

			For n = 1, there is only one 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, a solution that guarantees to find the princess in a(4)=4 nights is to search rooms (2,3,3,2).
For n = 5, a solution that guarantees to find the princess in a(5)=6 nights is to search rooms (2,3,4,4,3,2).
In the general case for n >= 3, a solution guaranteeing success in the minimum number of nights is to search rooms (2,3,...,n-1,n-1,...,3,2), so a(n) = 2*n - 4.

Christian Perfect, Solving the princess on a graph puzzle.
Puzzling Stack Exchange, Why does this solution guarantee that the prince knocks on the right door to find the princess?.
standupmaths, Youtube, The Castle and the Princess Puzzle.
Index entries for linear recurrences with constant coefficients, signature (2,-1).

Essentially the same as A005843, A004277 and A004275.

Cf. A130131, A130132, A331693, A386462.

CoefficientList[ Series[(2x^3 - x^2 + 1)/(x - 1)^2, {x, 0, 62}], x] (* Robert G. Wilson v, Mar 12 2018 *)
Join[{1,2},Range[2,200,2]] (* Harvey P. Dale, Jan 25 2019 *)

For n >= 3, a(n) = 2*n - 4.
From Chai Wah Wu, Apr 14 2024: (Start)
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)
E.g.f.: 4 + 2*exp(x)*(x - 2) + 3*x + x^2. - Stefano Spezia, Aug 15 2025

A387073 Record high points in A386482.

Original entry on oeis.org

1, 2, 4, 6, 9, 12, 14, 21, 25, 30, 33, 36, 38, 57, 65, 68, 93, 94, 141, 148, 150, 174, 177, 236, 244, 247, 260, 316, 393, 415, 428, 515, 635, 685, 951, 1055, 1067, 1315, 1388, 1516, 1639, 1828, 1903, 1969, 2841, 3235, 3342, 3414, 3592, 4516, 4936, 5948, 7444, 7652

Offset: 1

Michael De Vlieger, Aug 15 2025

nonn

Michael De Vlieger, Table of n, a(n) for n = 1..102

Cf. A386462, A387074.

Block[{c, j, k, m, p, r, nn},
  nn = 6000; c[] := False; m[] := 1; j = 2; c[1] = c[2] = True; r = 0;
  {1, 2}~Join~Monitor[Reap[Do[
    If[PrimePowerQ[j],
      Set[{p, k, m}, {#1, #1^(#2 - 1), #1^(#2 - 1)}] & @@
        FactorInteger[j][[1]]; While[And[c[k*p], k != 0], k--];
        If[k == 0, k = m; While[c[k*p], k++]]; k *= p,
      k = j - 1; While[And[Or[c[k], CoprimeQ[j, k]], k != 1], k--];
        If[k == 1, k += j; While[Or[c[k], CoprimeQ[j, k] ], k++] ] ];
    If[k > r, r = k; Sow[k]];
    Set[{c[k], j}, {True, k}], {n, 3, nn}] ][[-1, 1]], n] ]

A386463 Box which a player should open at step n to catch a cat performing a random walk through 8 boxes to minimize the escape rate of the cat.

Original entry on oeis.org

1, 7, 7, 1, 2, 2, 4, 7, 7, 2, 3, 4, 7, 1, 8, 7, 2, 3, 7, 7, 6, 2, 2, 3, 6, 8, 1, 8, 7, 6, 1, 2, 3, 4, 7, 1, 8, 7, 2, 3, 7, 7, 6, 2, 2, 3, 6, 8, 1, 8, 7, 6, 1, 2, 3, 4, 7, 1, 8, 7, 2, 3, 7, 7, 6, 2, 2, 3, 6, 8, 1, 8, 7, 6, 1, 2, 3, 4, 7, 1, 8, 7, 2, 3, 7, 7, 6

Offset: 1

Ruediger Jehn, Jul 22 2025

A cat is randomly hiding in one of 8 boxes, and a single player tries to catch the cat. In each step, the player opens a box. If the cat is found, the game ends; if not, the cat will move randomly either to the box on the left or to the box on the right. If the cat is in box 1 or 8, it has a 50% probability of escaping. By using the optimal strategy, the cat's escape rate is minimized to 0.223305988. The average duration of the game is 5.35 steps. Note that, since the problem is symmetric, a mirrored strategy also exists.

			a(1) = 1: 0.223306 is an upper bound for the minimum escape rate. If the player starts with box 2 (or 7) the escape rate exceeds this value at least after 11 steps no matter in which order the player will open the next boxes. If the player starts with box 3 (or 6) the escape rate exceeds the bound at least after 7 steps and if the player starts with box 4 (or 5) the escape rate exceeds the bound at least after 6 steps. Hence opening box 1 (or 8 for the mirrored strategy) allows the player to minimize the escape rate of the cat.

Ruediger Jehn, Optimal Strategies to Detect Randomly Walking Cat

Cf. A300576, A386462.

More terms from Jinyuan Wang, Jul 27 2025

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A387073 Record high points in A386482.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

A386463 Box which a player should open at step n to catch a cat performing a random walk through 8 boxes to minimize the escape rate of the cat.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions