|
To prove that every other move must be the small disc: after having moved it to a post, you have only one possible move that involves the other two posts -- and after doing that, your only chances will be either reversing the move you just did (not very wise...) or moving the smallest disc. QED.
For the cyclical part: consider the recursive algorithm for moving N discs from post A to post B being C the other post: move N-1 discs from A to C, move the N-th disk from A to B, move N-1 discs from C to B. If N=1, the smallest disc will obviously move in a cycle (a very short one!). And for larger N, the algorithm will produce two equivalent cycles, with an added move (the N-th disk) inbetween.
Finally, the algorithm. Let's suppose you want to move N discs from post 1 to post 3. The rule is: on every odd turn, move the smallest disc cyclically (if N is odd, make the cycle 1-3-2-1-3-2; if even, 1-2-3-1-2-3), and on every even turn do whatever you can that doesn't involve the smallest disc. |
