Sixth Graders’ Reasoning and Pattern Detection in Solving the Tower of Hanoi Puzzle

The Tower of Hanoi Puzzle is a fascinating mathematical puzzle invented by the French mathematician François Édouard Anatole Lucas in 1883 (the same Lucas after whom the Lucas Sequence, which works just like the Fibonacci Sequence with initial conditions 2 and 1, is named). It consists of three pegs and a set of circular disks of different sizes, each with a hole in the middle. There are two simple rules for moving the disks from one peg to another: 1. Only one disk may be moved at a time. 2. There can never be a larger disk on top of a smaller disk. The goal/solution to the puzzle is to determine the number of moves it takes to move n disks, denoted by H(n). There are two formulas for the solution, one recursive and one closed/explicit: 1. Recursive: H(n) = 2H(n - 1) + 1 2. Closed/explicit: H(n) = 2^n - 1 There is a myth that accompanies the puzzle. Buddhist monks in a tower in Hanoi, Vietnam move 64 golden disks from one peg to another according to the rules of the puzzle. When they are done, the world would end. According to the closed/explicit solution of the puzzle, this would require 2^64 – 1 = 18,446,744,073,709,551,615 moves! If it takes a mere one second per move, the puzzle would be solved in 584,542,046,091 years, which is about 42 times the current age of the universe! The focus of this analytic is on these sixth-grade students’ reasoning and problem solving as they detect patterns associated with the Tower of Hanoi Puzzle, even though at that point they have very limited knowledge of exponents. Researcher Robert B. Davis is the researcher in this analytic, and he briefly describes the aforementioned myth in Event 1, which seems to be familiar already to the students. However, instead of 64 (golden) disks, Researcher Davis’ version of the myth is that the world would end after the monks move 100 disks from one peg to another, which obviously would require many more moves than the 64-disk version. As Researcher Davis constructs a table on the chalkboard listing the number of disks and its corresponding number of moves, the students begin to notice several patterns. Mike and Milin are the first to notice the recursive solution in Event 2, which Michelle also notices in Event 3. Ankur is the first to notice the closed/explicit solution in Event 4, which he and four other students share with the class in Event 5. However, their closed/explicit solution is simply 2^n without subtracting 1. In Event 6, Mike and Matt notice a pattern that the first differences between consecutive pairs of the number of moves double with each disk, a pattern first noticed by Brian in Event 3. That’s actually the reason for the 2^n component of the closed/explicit solution. Matt notices another pattern in Event 7 that each first difference is always 1 greater than its initial number of moves. Finally in Event 8, the students use Bobby and Amy-Lynn’s proposed solution for the number of moves for 100 disks to determine after how many years would the world end according to the myth. Throughout this analytic, the students notice four different patterns regarding the Tower of Hanoi puzzle: 1. Recursive 2. Exponential 3. First differences 4. Relationship between the number of moves and the first differences When working on this complex and fascinating puzzle, these students at a young age were essentially modeling the work and behavior of mathematicians, to the interest of Researcher Carolyn A. Maher: “Fern [Hunt] outlined some of the things mathematicians do when they do mathematics. And I think it’s very interesting to watch the children in the tape do some of these same things. They do think of a simple problem, they do look for patterns, they look for finite differences- as you see. They notice the pattern and they notice that there’s an exponential here. They posit two to the n. And that’s what mathematicians do.” These students may have incorrectly calculated 2^100, and they may have overlooked the need to subtract 1, but even mathematicians are not always correct when working on unsolved/open problems and unproven conjectures (for example, when trying to prove Fermat’s Last Theorem for over three centuries!). The students indeed worked and reasoned collaboratively like mini-mathematicians on this complex task involving an exponential function despite their very limited knowledge of exponents. Task statement: Legend has it that there was a group of Buddhist monks in Hanoi, Vietnam who invented a puzzle called the Tower of Hanoi. These monks believed that once they solved the puzzle with 100 disks, the world would end. How many moves does it take to move 100 disks from one peg to another according to the rules of the puzzle, and when would the world end according to this myth? Video reference: https://doi.org/doi:10.7282/T3S46R6P Non-video references: 1. Hinz, A. M. (1992). Pascal’s Triangle and the Tower of Hanoi. The American Mathematical Monthly, 99(6), 538-544. 2. Mayansky, E. (2007). An Analysis of the Pedagogy of Robert B. Davis: Young Children Working on the Tower of Hanoi Problem. Unpublished doctoral dissertation, Rutgers University, NJ. 3. Rosen, Kenneth H., Discrete Mathematics and its Applications, 8th Edition, McGraw Hill. 4. Walsh, T. R. (1998). The Generalized Tower of Hanoi for Space-Deficient Computers and Forgetful Humans. Mathematical Entertainment, 20(1), 32-38