You may be familiar with the Tower of Hanoi puzzle in which you start with eight discs stacked on one of three pegs, each disc smaller than the one below it. The other two pegs are empty. The goal of the puzzle is to move the entire stack of discs to a different peg, according to the following rules:
Only one disc may be moved at a time, from the top position on one peg to the top position of a different peg.
No disc may ever be placed on top of a smaller one.
For convenience, we number the discs from 1 to 8 in order from smallest to largest. In this variation, you start with discs 1, 3, 5, and 7 on the first peg, and discs 2, 4, 6, and 8 on the second peg, as shown in Figure 1. Your goal is to end up with all eight discs in order on the third peg, following both rules (a) and (b). What’s the fewest number of moves needed to accomplish this goal, and how do you do it? How do you know your solution is minimal?
Figure 1: The starting position for Half-and-half Hanoi.
This problem originally appeared in the Prisoner’s Dilemma in the 2023 Spring issue of the PMP Newsletter. Solutions are no longer being accepted for this Dilemma.
Show solution?
Solution.
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 discs is by breaking the problem into shifting the top discs (using moves), followed by moving the th disc, followed by shifting the smaller discs back on top of it (using another moves). You can then solve the resulting recurrence relation .
Figure 2: Segregating Hanoi discs by parity.
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 moves to shift the top discs, one move of disc 8, moves to uncover disc 6, one move to put 6 on top of 8, moves to uncover disc 5 and one more to put it on 7, 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 , these phases total 182 moves, the minimum possible.
