Towers of Hanoi Puzzle: 3 Pegs, n Discs...Date: 11/15/97 at 22:47:52 From: Lauren Subject: A puzzle with 3 pegs, n discs, discs must be moved in size order from the first peg to the third My ninth grade advance placement geometry teacher has given me a Mathematics puzzle that I can't seem to answer. It has a name,she tells us, but won't tell us what the name is for fear we will go the easy way and look it up. It involves 3 pegs. We are told to find out the least number of moves it takes to get three discs in size order onto the third peg from the first. There are rules, however. You cannot hold a disc in midair while moving another, you cannot move more than one disc at a time, and a smaller disc can at no time be underneath a larger disc. I did this with 3 discs and it took me 7 moves. With four discs it took me 15 moves. At this point we are to devise a rule or formula for n discs. I'm going crazy trying to figure this out! Finally I turned to the Internet. You are my last hope! Please write back, I will be forever grateful if you can help me find the formula or give me the name of it. Thank you very much in advance! Lauren Date: 11/15/97 at 23:34:35 From: Doctor Pete Subject: Re: A puzzle with 3 pegs, n discs, discs must be moved in size order from the first peg to the third Hi, Well, I have to say that if your teacher did not give you the name of this puzzle for the reason she did, it would not be in the spirit of the problem for me to give it to you. It is a simple and famous problem, and the solution in the minimal number of moves is very elegant. However, I will give you a hint as to what your numbers are and why they are these particular values. 1) Calculate the number of moves for 1 disc (this is obvious!), and then 2 discs (also easy!). Compare this with the values you got for 3 and 4 discs, and make a table: number of discs: 1 2 3 4 5 6 number of moves: ? ? 7 15 ? ? Fill in as many of the question marks as you can. This will give you a clearer picture of what's going on. 2) Now, think of the puzzle like this: Suppose we have n discs, all of which are colored blue, except for the largest disc, which is red. Now, clearly, we must move all (n-1) of the blue discs before we may move the red. But notice there are only 3 pegs, and we are not permitted to move the red disc on top of any other disc (since it is the largest). So if we wanted to move the red disc to the third peg, two conditions must be satisfied: a) no disc is on peg 3 b) all blue discs are stacked (in order) on peg 2. Now, for these conditions to be true, how many moves must be made? Let this be a function of the number of blue discs = n-1. And if you then move the red disc, now how many moves have been made? (One more, right?) Finally, once we have moved the red disc onto peg 3, how many additional moves must be made to get the blue discs back on top of the red disc? (Obviously, the same number you needed to move them off!) So, how many in total? 3) If you did Hint 1, and followed Hint 2 very, very carefully, you should have the answer, and more importantly, you should know *why* the answer is the way it is. If you got confused, try thinking about Hint 2 with, say, 3 or 4 discs to begin with. 4) If you're *really* stuck, write back.... :) -Doctor Pete, The Math Forum Check out our web site! http://mathforum.org/dr.math/ Date: 11/16/97 at 07:00:32 From: Doctor Anthony Subject: Re: A puzzle with 3 pegs, n discs, discs must be moved in size order from the first peg to the third This is the 'Towers of Hanoi' problem. With n discs you need (2^n - 1) moves. -Doctor Anthony, The Math Forum Check out our web site! 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/