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.

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

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

Examples

			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.
		

Links

• Ruediger Jehn, Optimal Strategies to Detect Randomly Walking Cat

Crossrefs

Cf. A300576, A386462.

Extensions

More terms from Jinyuan Wang, Jul 27 2025