Marc Ditmore: Towers of Hanoi-a game of minimums
The Tower of Hanoi puzzle is a game that involves 3 pegs and 7 disks. The goal is to get all 7 disks from one peg to another moving 1 disk at a time and not putting a large disk on a small one. A minimum number of moves can be achieved for 3 pegs. This game is a classic example of a simple game with certain constraints but when the constraints are loosened (adding a peg) becomes very hard. In this talk we discuss the graphs associated with the Tower of Hanoi and generalized Tower of Hanoi puzzles in hopes of getting insight in to why adding more pegs makes the minimization problem so hard to solve.