The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
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.


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 

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

 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)?  
Contact me again if you need more information about all this.

-Doctor Terrel,  The Math Forum
 Check out our web site!   
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

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.