May 2004
Solutions:
Part 1:
One such answer is:
C: 6 12 16 17 26 31 38 47 48 56 61
B: 2 4 9 13 14 18 21 22 27 28 29 42 45 49 52 53 59 62
It is known that for k=1,2,...,64, it will require 2^(k-1) moves if we want to move disk numbered k from, say, "A" to "B", and then pile all the smaller disks on top, assuming that initially the smaller disks are all on "C". If any smaller disks are elsewhere, we have to move them to "C" first. So there is a natural way to look at the present configuration and write down the binary expansion of the minimum number of moves. Working from largest to smallest, ask whether we need to move disk k before acting on the next larger disk that needs moved.
The binary expansion of the number of moves is
00101011 10011001 00101101 11011111
10100010 00110010 01001001 11010110
To go in the reverse direction, from the binary number to the configuration, we again start with the largest disk and work down. Among disks that we've placed so far, the smallest that needs to move has its source and destination determined; the peg that is neither the source nor destination will be called the "distinguished peg" for this move. If the next bit is "0", we place the new disk on the "distinguished peg" (if the smallest disk that we've placed so far wants to move from "B" to "A", then the distinguished peg is "C" and the new disk will be placed on "C"). If the next bit is "1", we place the new disk on either of the two other pegs ("B" or "A" in this example).
We still have to satisfy the requirement of the initial number of disks on each peg. We had chosen this configuration to have the least number on "C", and secondly, subject to that, have the least number on "B". We call this our "figure of merit".
We use a technique called "dynamic programming". We work from largest (1) to smallest (64), always maintaining three possible configurations. At time k, we have three possible configurations for the largest k disks: for each target peg "A", "B", "C", we keep a configuration for which the "distinguished peg" is this target peg, and for which the figure of merit is optimized. If the next bit is "0", we just place the new disk on the "distinguished peg" (for each of the three configurations) and continue. If the bit is "1", we have two choices of where to put the new disk; if the "distinguished peg" is "B", we could place the disk on "C" and the new "distinguished peg" will be "A". Among the 6=3*2 resulting configurations, two will have distinguished peg "A"; we select one that optimizes the figure of merit. When we have gone through all 64 disks, we still have three strings. Pick one that optimizes the figure of merit, and we're done.
Part 2:
Observation 1:
Let us define the direction from A to B to C to A as the "clockwise" direction, and the direction from A to C to B to A as the "counter-clockwise" direction. When moving the tower of size 64 from A to B, the largest disk makes only one move, namely the one from A to B, so its movements are identical to those of the tower. In the commonly known recursive solution, one performs a single clockwise step of a tower of size n using two counter-clockwise steps of a tower of size n-1. Similarly, if we had wanted to move a tower of size n counter-clockwise, we would have done so by two clockwise steps of a tower of size n-1. Therefore, in order to move the disk of size 64 clockwise, the disk of size 63 only moves counter-clockwise, the disk of size 62 only moves clockwise, etc. In general, when a disk of size n moves, it will always move clockwise if the parity of n is even, and will always move counter-clockwise if it is odd.
Observation 2:
Note that if the disk of size "1" moved at the last step, it can not move in the next step. This would have indicated that the last step was redundant. If, however, the disk of size "1" did NOT move in the last step, then it MUST move in the next. In order to show this, let us look at the top-most disks in each peg. Let us assume that the top of peg "a" is "1", the top of peg "b" is "m" and the top of peg "c" is "h", where 1<m<h. If "1" was not the one to move last, then it must have been "m". "h" could not have moved, because if it moved from either "a" or "b" then it was placed, before, on top of a disk smaller than itself. Likewise, "m" could not have moved from "a", so it must have moved from "c". If in the next move "1" does not move, then the only choice is for "m" to move back to "c", once again indicating that "m"'s move was redundant. Therefore, disk "1" must move at every alternating step. (Note that this property can be extended through recursion: disk "2" only moves in steps that are 2 modulo 4, disk "3" only moves in steps that are 4 modulo 8, etc. We will not use this property in the solution, however.)
Using these observations, it is now possible to tell what the next move is, given the top-most disks on each peg, with only one extra bit of information, namely the parity of the number of moves made so far. If this parity is even, disk "1" will have to be moved one step counter-clockwise. If the parity of moves is odd, there is only one move that can possibly be executed that does not involve moving disk "1".
However, this bit, too, can be divined from the state of the pegs. Consider the state where the top of peg "a" is "1", the top of "b" is "m" and the top of "c" is "h" with 1<m<h. We are at a dilemma whether to move disk "1" or disk "m". This dilemma actually involves whether disk "1" is the next disk to move and disk "m" is the one that moved in the previous step, or whether disk "m" is the one that will move in the next step and disk "1" was already moved in the previous step.
Note, however, that if "m" moves in the next step, it will move from "b" to "c", whereas if it already moved in the last step, it moved from "c" to "b". One of these directions is clockwise, the other is counter-clockwise. Therefore, only one of them can be a legal move for a disk of size "m" (as determined by the parity of m).
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com