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/