Tower of Hanoi solutions for non-legal initial configuration I just found an Towers of Hanoi game (see http://en.wikipedia.org/wiki/Tower_of_Hanoi) messed up by a someone to one tower not obeying the rules, eg. large and small disks where interleaved. I just played the game to the rules, and finally came up with an usual legal solution.
I tried different non-legal initial towers on one one stack, and all proved solvable.
Is every initial configuration with all disks in one tower solvable?
 A: Yes; this can be proved by induction on $n$, the number of disks. In fact, it’s easier to prove something even stronger: no matter how the disks are distributed on the three spindles, it’s possible to get them properly arranged on one spindle using only legal moves.
This is certainly true when $n=1$. Suppose that it’s true for all arrangements of at most $n$ disks, and let $\langle T_1,T_2,T_3\rangle$ be some arrangement of $n+1$ disks, where $T_k$ is the tower on spindle $k$. One of the towers contains the largest disk; we might as well assume that it’s $T_1$. Suppose that there are $b$ disks on $T_1$ below the largest disk; then we can pretend that the largest disk is really the base of the tower on spindle $1$, and that we have an arrangement of the $(n+1)-(b+1)=n-b\le n$ disks on $T_2$ and $T_3$, and on $T_1$ above the largest disk. By the induction hypothesis we can get all $n-b$ of these disks onto a single spindle in the correct order. If they end up on the biggest disk instead of on one of the other two spindles, use the usual solution to move them to another spindle. Then we can move the largest disk to an open spindle. Once again we pretend that it’s the base of its spindle instead of a disk, so we have in effect an arrangement of the other $n$ disks. By the induction hypothesis it can be solved, and if necessary we can then use the usual solution to move the resulting tower of $n$ disks onto the largest disk, completing the solution.
