IBM Ponder This #312 · April 2024

The Tower of Hanoi game consists of three rods and $n$ disks of different sizes (denoted by $1,2,\dots ,n$) that can slide onto any rod. The initial state of the game consists of all the disks on one rod in ascending order, with disk $1$, the smallest and lightest of the disks on top.

Each move in the game consists of choosing one rod, picking up the top disk from that rod, and placing it on another rod. Such a move is allowed only if the disk being moved is smaller than the top disk on the target rod, or if the target rod is empty.

If the three rods are placed on different points on a circle, at any given state, there are three possible moves:

0. Take disk "1" from its rod and move it clockwise to another rod.
1. Take disk "1" from its rod and move it counterclockwise to another rod.
2. Take a disk which is not "1" and move it to another rod.

Move 2 will not always be available, such as when all the disks are currently located on one rod. In such instances, we say that Move 2 does nothing. In all other cases, there is only one legal way to perform Move 2.

We can describe the flow of games using a string describing moves. For example, "0202020", when performed on the initial state of a game with $n=3$, moves all the disks one rod clockwise. We call the state where all the disks are on the clockwise-located rod the winning state of the game. Another way to describe that game is with the string "02" which must be performed for exactly 7 steps, with the convention that once the end of the string is reached, we start over at the beginning. It can be shown that the $n$-disk game is won by using the string "02" for $2^n-1$ steps with $n$ odd, and "12" for $2^n-1$ steps with $n$ even.

For example, when $n=3$ and the move string is "0202112", after 8 steps the winning step is reached, and the next step does nothing, so we say the winning state is reached both on step 8 and step 9. Similarly, for $n=4$ and move string "200211", the winning state is reached after 41 and 122 moves. However, if we start two simultaneous games, one with $n=3$ and "0202112", and the other with $n=4$ and "200211", and perform each step in both games at the same time, both games will reach a winning state together for the first time after 932 steps.

Your Goal: For the two games defined by $n=7$ and "12021121120020211202121", and $n=10$ and "0211202112002", find the minimal number of steps at which both games reach a winning state at the same time.

A Bonus "*" will be given for finding the minimal number of steps such that both the above games and also the game defined by $n=9$ and "20202020021212121121202120200202002121120202 112021120020021120211211202002112021120211200212112020212120211" reach a winning state for the first time.

Solution

Best opened after a real attempt

To be added.