You can approach this puzzle in a slightly different manner.
If you label the disks instead of the pegs, and then list the disk that's moved with each step, the binary nature of the solution becomes apparent.
Let's label the smallest disk 1, the next larger disk 2, and so on.
Moving a tower of N disks then proceeds recursive
- Move disks 1 through N-1 out of the way, as if there were no other disks.
- Move disk N.
- Move disks 1 through N-1 back on top of disk N.
To move one disk, you obviously move disk 1. To move two disks, move disk 1, move disk 2, then put disk 1 on top of it.
The string of disks to be moved with each step
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 ....
Also notice that the number of the disk you move is the least order bit1
of the binary number representing the step number.
To solve an actual "Tower of Hanoi" problem, keep two rules in mind:
The tower can only be moved if you never put an odd-numbered disk on top of another odd-numbered disk without an even-numbered disk in between. Also, never put an even-numbered disk on an even numbered disk.
- In order to move an odd number of disks to a particular peg, start by moving the first disk to that peg. For an even number of disks, move the first disk to the other peg.
Following the above rules plus the disk-numbering string leads to a unique solution of exactly 2N
-1 steps for N disks.
If the monks are able to move a disk once a second, it will take 584,542,046,090 years, 228 days, 15 hours, 14 minutes, and 45 seconds to move the entire tower of 64 disks!
Or the least-order bit, minus one, depending on how you number the bits.