Sometimes I am genuinely surprised when a fun game or idea I was exposed to in elementary school is unknown by my older students. The Towers of Hanoi problem fits the description. A number of students immediately gravitated towards the game as they entered. And after a quick explanation of the rules, they got down to business:
An online, interaction version of the game was also running on my projector, which generated some class discussion of strategy. Students were able to solve many of the early challenges, and we began to look for the most efficient methods, sharing our findings on the board.
- 1 disc, 1 move
- 2 discs, 3 moves
- 3 discs, 7 moves
- 4 discs, 15 moves
From here, some students conjectured that 5 disks must take 15 moves….but nothing is quite that easy, and I asked them to prove or show it. During classwork time, I heard discussion of possible formulas. Since we have been working with both explicit and recursive formulas, this was an effective way to discuss the differences between them, and why we might prefer one over the other.
The explicit formula sure is nice, but the recursive provides a roadmap for solving the problem for any number of disks.