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

### Pascal's Triangle and the Tower of Hanoi

```
Date: 08/07/97 at 19:03:47
From: Laura Flynn
Subject: Pascal's Triangle and the Tower of Hanoi

Hi there...

I can vaguely remember a connection between Pascal's Triangle and
the "Tower of Hanoi" game.  Actually, all I really remember is that
there is a connection; I can't remember what it is!  Can you help?

The Tower of Hanoi is that game where you have three vertical rods
and on the left rod you have seven discs stacked in order of diameter
(big on the bottom, small on top). You have to move all the discs to
the righthand rod in the least number of moves possible. The only
restriction is that you can never put a large-diameter disc on top of
a smaller one (you can only put a small on a larger one).

I think Pascal's Triangle can be used to predict the least number of
moves possible for any number of discs (and rods?).

Sorry!  That's all the information I remember. It would be interestng
to know another application of Pascal's Triangle.

Thanks...
Laura
```

```
Date: 08/10/97 at 15:30:33
From: Doctor Terrel
Subject: Re: Pascal's Triangle and the Tower of Hanoi

Dear Laura,

The relation between Pascal's Triangle and the Tower of Hanoi, as you
stated, concerns the number of moves required to reposition a given
disc to another rod (with all the smaller discs on top). It goes like
this:

The sum of the entries of the nth row of Pascal's Triangle is 2^(n-1).

Row
1 1  = 2^0 = 1
2 1  1  = 2^1 = 2
3 1  2  1  = 2^2 = 4
4 1  3  3  1 = 2^3 = 8
5 1  4  6  4  1 = 2^4 = 16

nth row  = 2^(n-1)

Now as one does the Tower puzzle and pays careful attention to how
many moves are required to position a given disc on a rod (with all
the smaller ones on top, of course), a similar pattern is observed.
The first disc needs only 1 move.  The 2nd disc needs 2.  The 3rd
needs 4.  The 4th needs 8.  And so on.  (I'm assuming here that you
know how to do these moves with the minimum number of transfers.)

We can say: to arrange the nth disc, 2^(n-1) moves are required.

Another point: don't forget to teach the students about the grand
total of moves to do the Tower puzzle.  To realign, say 5 discs, one
must make 1+2+4+8+16 = 31 moves.  This brings up the well-known
formula: 1+2+4+8+ ... + 2^n = 2^(n+1) - 1.

And finally: are you aware of how the famous Wheat on a Chessboard
problem fits into the picture (the one about the invention of chess)?

-Doctor Terrel,  The Math Forum
Check out our web site!  http://mathforum.org/dr.math/
```
Associated Topics:
High School Permutations and Combinations
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