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.

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, 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, 7, 7, 5, 2, 4, 7, 2, 5, 5, 2, 7, 4, 2, 5, 7, 7, 5, 2, 4

Offset: 1

Author

Ruediger Jehn, Jul 22 2025

Keywords

• nonn
• hard

Comments

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.

Examples

			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.
		

Links

• Ruediger Jehn, Optimal Strategies to Detect Randomly Walking Cat

Crossrefs

Cf. A300576, A386463.

Extensions

More terms from Jinyuan Wang, Jul 29 2025