Associated Topics || Dr. Math Home || Search Dr. Math

### 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

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/

Associated Topics:
High School Puzzles
Middle School Puzzles

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search