cp's OEIS Frontend

A386462 Box which a player should open at step n to catch as fast as possible a cat performing a random walk through 8 boxes.

%I A386462 #15 Aug 04 2025 19:13:42
%S A386462 4,7,5,2,7,4,2,5,7,7,4,2,2,4,7,7,4,2,2,4,7,7,4,4,7,2,4,7,2,5,5,2,7,4,
%T A386462 4,7,2,5,5,2,7,4,4,7,2,5,5,2,7,4,4,7,2,5,5,2,7,4,4,7,2,5,5,2,7,4,2,5,
%U A386462 7,7,5,2,4,7,2,5,5,2,7,4,2,5,7,7,5,2,4
%N A386462 Box which a player should open at step n to catch as fast as possible a cat performing a random walk through 8 boxes.
%C A386462 A cat is randomly hiding in one of 8 boxes and a single player tries to catch the cat. In each step, first the player opens a box, if the cat is found, the game is finished, if not the cat will move randomly one box to the left or one box to the right. If the cat is in box 1 it can only move to box 2 in the next step. A safe strategy to find the cat in no more than 12 steps is to open the boxes in this order: 2,3,4,5,6,7,7,6,5,4,3,2. On average this strategy takes 25963/4096 (6.339) steps to catch the cat. However, applying the strategy to open box a(n) at step n reduces the average duration of the game to 4.749593 which is a factor of 1.335 faster. Note, since the problem is symmetric also a mirrored strategy exists.
%H A386462 Ruediger Jehn, <a href="/A386462/a386462.pdf">Optimal Strategies to Detect Randomly Walking Cat</a>
%e A386462 a(1) = 4: If the player starts with box 1 (or 8) the average duration of the game exceeds the value of 4.7496 at least after 10 steps no matter in which order the player will open the next boxes. If the player starts with box 2 (or 7) the average duration of the game exceeds the value of 4.7496 at least after 25 steps and if the player starts with box 3 (or 6) the average duration of the game exceeds the value of 4.7496 at least after 11 steps. Hence opening box 4 (or 5 for the mirrored strategy) allows the player to catch the cat in the fastest way.
%Y A386462 Cf. A300576, A386463.
%K A386462 nonn,hard
%O A386462 1,1
%A A386462 _Ruediger Jehn_, Jul 22 2025
%E A386462 More terms from _Jinyuan Wang_, Jul 29 2025