The Hanoi coins game

As the coins accumulate, they naturally form "double towers," or towers with layers of two coins of equal radius. We know from the traditional tower of Hanoi game that the minimum number of moves to transfer a tower with $n$ coins of different radii is $2^n - 1$ , so the minimum number of moves to transfer a double tower with $2n$ coins is $2(2^n - 1)$ . With this understanding, we can find a recurrence relation that gives the minimum number of moves to construct a double tower with $2n$ coins. To swap towers, we construct a double tower on $S_3$ and then deconstruct it in mirror reverse order (i.e., by replacing moves to or from $S_1$ with moves from or to $S_2$ and performing the moves in reverse).

Suppose $A$ and $B$ have $n$ coins each, and label the coins in increasing order of radius $a_1, \dots, a_n, b_1, \dots, b_n$ . Let $u_n$ and $v_n$ denote the minimum number of moves to combine $A$ and $B$ into a double tower of $2n$ coins on $S_2$ and $S_3$ , respectively, and let $w_n$ denote the minimum number of moves to swap $A$ and $B$ . To combine $A$ and $B$ on $S_2$ , we must

• construct a double tower with $2n - 2$ coins on $S_3$ ,
• move $a_n$ on top of $b_n$ , and then
• transfer the double tower on top of $b_n$ and $a_n$ .

The minimum number of moves for this process is $u_n = v_{n - 1} + 1 + 2(2^{n - 1} - 1).$ To combine $A$ and $B$ on $S_3$ , we can

• construct a double tower with $2n - 2$ coins on top of $b_n$ on $S_2$ ,
• move $a_n$ from $S_1$ to $S_3$ ,
• transfer the double tower from $S_2$ to $S_1$ ,
• move $b_n$ on top of $a_n$ on $S_3$ , and then
• transfer the double tower from $S_1$ to $S_3$ .

We also could have started by constructing the double tower on $a_n$ , but that would not have changed the minimum number of moves, which is $v_n = u_{n - 1} + 1 + 2(2^{n - 1} - 1) + 1 + 2(2^{n - 1} - 1).$ To swap $A$ and $B$ , we can

• construct a double tower with $2n$ coins on top of $b_n$ on $S_2$ ,
• move $a_n$ to $S_3$ , and then
• transfer the double tower on to $a_n$ on $S_3$ .

Again, we could have started by building the double tower on top of $a_n$ , but that would not change the minimum number of moves for these steps, which is $u_n + 1 + 2(2^n - 1).$ Whatever sequence of moves we use for the three steps above, we can move $b_n$ to $S_1$ and then apply the mirror reverse sequence to reconstruct the towers in swapped positions. The minimum number of moves to swap the towers is then $w_n = 2[u_{n - 1} + 1 + 2(2^{n - 1} - 1)] + 1.$ From these recurrence relations and the initial conditions $u_1 = 1$ , $v_1 = 2$ , and $w_1 = 3$ , we can compute $u_n$ , $v_n$ , and $w_n$ for all $n$ . The first few values are given in the following table.

When $n = 4$ , the minimum number of moves to swap the towers is $w_4 = \boxed{59}$ .