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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.