The Prisoner's Dilemma

The Prisoner’s Dilemma received solutions from PMP participants William Keehn and Robert Noll; we follow primarily the former. First show that the minimum number of moves to solve the usual Tower of Hanoi puzzle with $n$ discs is $H_n=2^n-1,$ by breaking the problem into shifting the top $n-1$ discs (using $H_{n-1}$ moves), followed by moving the $n$th disc, followed by shifting the $n-1$ smaller discs back on top of it (using another $H_{n-1}$ moves). You can then solve the resulting recurrence relation $H_n=2H_{n-1}+1$.

Now consider the problem Prof. Hinz poses. Note that every move is reversible, so if you were to play a film of the optimal solution backward, it would necessarily be the optimal way to turn a pile of eight discs into the configuration shown in Figure 1. But to accomplish this task, you must first use $H_7$ moves to shift the top discs, one move of disc 8, $H_5$ moves to uncover disc 6, one move to put 6 on top of 8, $H_4$ moves to uncover disc 5 and one more to put it on 7, $H_2$ moves to uncover disc 3 and one more to put it on disc 5, and two final moves to put disc 1 on 3 and disc 2 on 4. (This sequence of events is beautifully depicted in William’s drawing shown in Figure 2.) Using the formula for $H_n$, these phases total 182 moves, the minimum possible.