Towers of Hanoi Proof

March 27, 2012

This is the Towers of Hanoi.
The puzzle is almost intuitive: how can you move the tower from the left peg to the right without placing any larger disks on top of any smaller disks.

Wikipedia has this animated gif of a solution for four disks. A mathematical question that a natural followup:
how many moves does it take to solve the puzzle with n disks?

A 4th grade student of mine took on a harder variation of this puzzle: how do you solve the puzzle–and count the number of moves–if you can only move disks one peg at a time. Notice that the gif above does not give a solution for this harder variation.

His solution was so excellent that I wanted to showcase it here. First of all, it’s a perfect example of how to use induction. Second, it’s personal–I love it when students use exclamation marks, because it shows that they’re really involved with the math as a story. Third, it’s concise. Fourth, it’s powerful. Fifth, pursuing this was his decision: he learned about the puzzle in Katherine’s How to Count Your Way Out of Trouble at the Robinson Center, and wanted to follow it to its full conclusion on his own. (If he hadn’t, I wouldn’t have suggested induction as a method of proof. ) This is exactly the experience of math I want my students to have.

Notify of

Inline Feedbacks
View all comments