Tower of HanoiDate: 10/16/97 at 00:59:22 From: Forrest Bankston Subject: Tower of Hanoi I'm looking for mathematical solution, not a trial and error one. I have done several net searches but can find no solution - just histories of the puzzle and games for trial-and-error fun. My students are exasperated and want a mathematical model. Can you help? Muchly appreciated... Forrest Date: 10/16/97 at 10:15:49 From: Doctor Rob Subject: Re: Tower of Hanoi Problem 1: Move one disk from the top of pile A to pile B. Solution 1: Do it! Problem 2: Move a stack of the two smallest disks from the top of pile A pile to pile B. Solution 2: Move the small disk to the pile C. Move the large one to pile B. Move the small one to pile B. Problem 3: Move a stack of the three smallest disks from the top of pile A to pile B. Solution 3: Use Solution 2 (relabeling the piles B <-> C) to move the two smallest disks to pile C. Move the largest one to pile B. Use Solution 2 (relabeling the piles A <-> C) to move the two smallest ones to pile B. Problem 4: Move a stack of the four smallest disks from the top of pile A to pile B. Solution 4: Use Solution 3 (relabeling the piles B <-> C) to move the three smallest disks to pile C. Move the largest one to pile B. Use Solution 3 (relabeling the piles A <-> C) to move the three smallest ones to pile B. Problem 5: ... Solution 5: ... ... Problem n: Move a stack of the n smallest disks from the top of pile A to pile B. Solution n: Use Solution (n-1) (relabeling the piles B <-> C) to move the n-1 smallest disks to pile C. Move the largest one to pile B. Use Solution (n-1) (relabeling the piles A <-> C) to move the n-1 smallest ones to pile B. The trick is in keeping track of the relabeling during the process! Example: Move 4 disks from X to Y: X Y Z Start: 1234 - - 1. Move 1 from X to Z: 234 - 1 2. Move 2 from X to Y: 34 2 1 3. Move 1 from Z to Y: 34 12 - 4. Move 3 from X to Z: 4 12 3 5. Move 1 from Y to X: 14 2 3 6. Move 2 from Y to Z: 14 - 23 7. Move 1 from X to Z: 4 - 123 8. Move 4 from X to Y: - 4 123 9. Move 1 from Z to Y: - 14 23 10. Move 2 from Z to X: 2 14 3 11. Move 1 from Y to X: 12 4 3 12. Move 3 from Z to Y: 12 34 - 13. Move 1 from X to Z: 2 34 1 14. Move 2 from X to Y: - 234 1 15. Move 1 from Z to Y: - 1234 - Notice the pattern of the disk being moved: 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1. On all odd numbered moves, you are moving disk 1. If the move number is 2 times an odd number, you are moving disk 2. If the move number is 4 times an odd number, you are moving disk 3. In general, if the move number is 2^n times an odd number, you are moving disk n+1. Notice Steps 1-3 are Solution 2 with A = X, B = Y, C = Z. Notice Steps 5-7 are also Solution 2 with A = Y, B = Z, C = X. Notice Steps 9-11 are also Solution 2 with A = Z, B = X, C = Y. Notice Steps 13-15 are also Solution 2 with A = X, B = Y, C = Z. Notice Steps 1-7 are Solution 3 with A = X, B = Z, C = Y. Notice Steps 9-15 are also Solution 3 with A = Z, B = Y, C = X. You can plan the whole operation ahead. There will by 2^d-1 moves if there are d disks. Move 2^(d-1) will be to move the largest disk from X to Y. To do that, you must move the d-1 smaller disks off of X, but not put them at Y, but at Z. That will take Steps 1 through 2^(d-1)-1. Afterwards, you have to move the d-1 smaller disks from Z to Y. That will take Steps 2^(d-1)+1 to 2^d-1. That divides the problem into two smaller ones of the same kind. Now you plan each of those in a similar way: the middle step will be moving the largest disk from its starting place to the appropriate destination. The preceding steps will be to get the smaller disks out of the way, and the following steps will be to move the smaller disks to the destination. Understood? If not, write back, and we'll try to explain further or differently. -Doctor Rob, The Math Forum Check out our web site! http://mathforum.org/dr.math/ Date: 10/16/97 at 14:14:07 From: Forrest Bankston Subject: Re: Tower of Hanoi Got it! Thanks for the quick turnaround and detailed explanation. - Forrest |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/