Towers of HanoiDate: 10/08/2000 at 10:22:15 From: Rakesh Subject: Towers of Hanoi formula and how to get there What is the general formula for finding the fewest number of moves required to finish Towers of Hanoi with n disks, apart from 2^n - 1? I also need to know how to prove it works and how you got there. Thank you. Date: 10/08/2000 at 10:35:39 From: Doctor Anthony Subject: Re: Towers of Hanoi formula and how to get there The rules for Towers of Hanoi can be found our "Towers of Hanoi" FAQ: http://mathforum.org/dr.math/faq/faq.tower.hanoi.html The formula for the minimum number of moves with 3 pegs and n discs is 2^n - 1. The recurrence relation that leads to this result is u(n) = 2*u(n-1) + 1 .....................................[1] where u(n) is number of moves with n disks present. To see this, note that to transfer n disks to another peg we must first transfer the top n-1 disks to the third peg (taking u(n-1) moves) then transfer the largest disk to a vacant peg (1 move) and then transfer n-1 disks back to the peg with the largest disk (taking another u(n-1) moves.) Adding these moves we get u(n-1) + 1 + u(n-1) = 2*u(n-1) + 1 Solving this recurrence relation gives u(n) = 2^n - 1 To prove this result you can either use a descending series of partial sums based on the recurrence relation (1) above, leading to 1 + 2 + 2^2 + 2^3 + ..... + 2^(n-1) = (2^n -1 )/(2-1) = 2^n - 1 or you can prove the result by induction. Inductive Proof --------------- First show that the formula is true for n = 1. For n = 1 the formula gives 2^1 - 1 = 1 and that is correct. Next assume it is true for some value n = k, that is we assume the truth of u(k) = 2^k - 1 Now add one more disk, so that n = k+1. From the recurrence relation (1) we have u(k+1) = 2*u(k) + 1 = 2(2^k - 1) + 1 = 2^(k+1) - 2 + 1 = 2^(k+1) - 1 and this is the same equation we had before, except that k is replaced by k+1. So if the result is true for n = k, then it is true for n = k+1. But it is true for n=1, therefore it will be true for n = 2, and if true for n = 2 it will be true for n = 3, and so on to all positive integral values of n, by the Principle of Mathematical Induction. - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/ |
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/