I am studying the Tower of Hanoi, and as I read through some posts on here about the proof of optimality for the optimal solution, I found a comment that said there cannot be deadlocks in the TH game. I took it to mean that the game is always solvable and set out to try proving this statement. However, I ended up with a legal-looking configuration that seems unsolvable.
Consider a game with $3$ pegs and $7$ disks, whose sizes are represented by $1, 2, 3, 4, 5, 6, 7$.
$$\begin{array}[b]{c} 2 \\ 3 \\ \text{Peg 1} \\ \end{array} \quad \begin{array}[b]{c} 1 \\ 7 \\ \text{Peg 2} \\ \end{array} \quad \begin{array}[b]{c} 4 \\ 5 \\ 6 \\ \text{Peg 3} \\ \end{array} $$
I believe this configuration is not possible. However, I can't seem to find a way to prove it. Please advise!
I'm not sure if I should start a separate thread for this, but I'd greatly appreciate it if someone could provide some insights into how one may approach proving the solvability of TH game, just in case I couldn't prove it myself. If you do, please indicate this part from the rest of your answer so I could recognize it and stop reading further. Thank you!
Disks $1$ through $6$ can be sorted and stacked onto peg $3$ with the following sequence of moves:
$$1 \to 3 \\ 2 \to 2 \\ 1 \to 2 \\ 3 \to 3 \\ 1 \to 1 \\ 2 \to 3 \\ 1 \to 3, $$ where the notation $a \to b$ means moving disk $a$ to peg $b$. Since it is possible to sort the first $6$ disks onto a single peg, it is possible to move disk $7$ to a different peg--in this case, peg $1$ if it was not already on $1$. If disk $7$ was already on peg $1$, then the standard sequence of moves of the stack $1$-$6$ on peg $3$ will move it onto disk $7$, solving the puzzle.