Interrupted Tower of Hanoi
[1 Apr 2026]Q: ??? The Tower of Hanoi puzzle consists of n disks each with a hole in the middle, stacked in decreasing order of size on post 1 of three posts. The puzzle is to transfer the stack from post 1 to post 3, subject to the conditions that only one disk may be moved at a time, and that a disk may never be placed on a smaller disk. The puzzle has a well-known recursive solution:
- Move the stack of the top n - 1 disks from post 1 to post 2.
- Move the largest disk from post 1 to post 3.
- Move the stack of the top n - 1 disks from post 2 to post 3.
This solution takes 2n - 1 moves, and is the best possible.
Suppose that you come across a Tower of Hanoi set with an arrangement of disks on the three posts, with the disks on each post stacked in decreasing order as usual.
- Can you quickly determine whether this position is one that occurs during the solution above?
- Whether or not this position occurs during the solution above, it is possible to start from this position and move the disks to post 3. What move should you perform first?