Optimal Strategies to Catch Randomly Walking Cat

The optimal strategies to catch a randomly walking cat in various environments are presented. All games have a player that opens a box at step $i$. If the cat is in this box the player wins, if not, the cat moves randomly to an adjacent box, or in case the box is open to the outside, the cat may escape. If the cat is not escaping, the next step of the game is played. In case the cat has doors to escape, the optimal strategy is determined that minimizes the escape chances of the cat. If there are no doors to the outside, the strategies are calculated that minimize the game duration. The environments are 1) a one-dimensional array of up to 9 boxes in a line 2) this line is connected to a ring and 3) a $2 \times m$ grid (with $2\le m\le 4$) of boxes. In cases 1) and 3) the boxes may or may not have exits to the outside. Numerical proofs for the optimality of the presented strategies are outlined. Also a formula is presented for the average number of steps it takes a randomly walking cat to exit a $2\times m$ grid when no player is involved. This formula is only based on Fibonacci numbers if $m$ is even and Lucas numbers if $m$ is odd.