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

-Doctor Terrel,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/