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

%I A300576 #68 Aug 16 2025 10:03:55
%S A300576 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,
%T A300576 48,50,52,54,56,58,60,62,64,66,68,70,72,74,76,78,80,82,84,86,88,90,92,
%U A300576 94,96,98,100,102,104,106,108,110,112,114,116,118,120,122
%N 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).
%C A300576 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?
%C A300576 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
%C A300576 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".
%H A300576 Christian Perfect, <a href="https://www.checkmyworking.com/2011/12/solving-the-princess-on-a-graph-puzzle/">Solving the princess on a graph puzzle</a>.
%H A300576 Puzzling Stack Exchange, <a href="https://puzzling.stackexchange.com/questions/455/why-does-this-solution-guarantee-that-the-prince-knocks-on-the-right-door-to-fin">Why does this solution guarantee that the prince knocks on the right door to find the princess?</a>.
%H A300576 standupmaths, Youtube, <a href="https://www.youtube.com/watch?v=nv0Onj3wXCE">The Castle and the Princess Puzzle</a>.
%H A300576 <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (2,-1).
%F A300576 For n >= 3, a(n) = 2*n - 4.
%F A300576 From _Chai Wah Wu_, Apr 14 2024: (Start)
%F A300576 a(n) = 2*a(n-1) - a(n-2) for n > 4.
%F A300576 G.f.: x*(2*x^3 - x^2 + 1)/(x - 1)^2. (End)
%F A300576 E.g.f.: 4 + 2*exp(x)*(x - 2) + 3*x + x^2. - _Stefano Spezia_, Aug 15 2025
%e A300576 For n = 1, there is only one room to search, so a(1) = 1.
%e A300576 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.
%e A300576 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.
%e A300576 For n = 4, a solution that guarantees to find the princess in a(4)=4 nights is to search rooms (2,3,3,2).
%e A300576 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).
%e A300576 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.
%t A300576 CoefficientList[ Series[(2x^3 - x^2 + 1)/(x - 1)^2, {x, 0, 62}], x] (* _Robert G. Wilson v_, Mar 12 2018 *)
%t A300576 Join[{1,2},Range[2,200,2]] (* _Harvey P. Dale_, Jan 25 2019 *)
%Y A300576 Essentially the same as A005843, A004277 and A004275.
%Y A300576 Cf. A130131, A130132, A331693, A386462.
%K A300576 nonn,easy
%O A300576 1,2
%A A300576 _Dmitry Kamenetsky_, Mar 09 2018