The Tower of Hanoi

The object is to move all the blocks from the left peg to the right peg. You can move the blocks one at a time from any peg to another by clicking and draging the mouse. The only restriction is that a larger block can never be placed on a smaller block.

Although you may find it interesting to play this game, it is a lot more fun to anaylze the game. In particular, how many moves does it take if you play the game in an optimal manner ? It is clear that it takes T₁ = 1 move if there is one block, and it takes T₂ = 3 moves if there are 2 blocks, and T₃ = 7 moves if there are 3 blocks. Can you see the pattern ? How many moves T_n+1 does it take to move n + 1 blocks in terms, the number of moves T_n it takes to move n blocks ? Once you find the relationship between T_n+1 and T_n, you have essentially solved the problem.

[Next]	Head to Head Tetris
[Up]	Interactive Math Games
[Home]	Home Page
[Mail]	Send EMail to Maine Math Talent Search
[Contents]	Maine Math Talent Search Contents

Last modified on Tuesday, January 12, 1999