Presentation

Mathematical communication

Personal engagement

Reflection

Use of mathematics

The Towers of Hanoi (ToH) is a mathematical puzzle that consists of multiple pegs(usually three) and disks (usually four). For this assessment, I will be assuming that there are three pegs and four disks. In the beginning, all of the four disks should be in the left peg (peg A) with the smallest (disk A) on the top, 2nd smallest (disk B) below, 3rd smallest (disk C) below that, and finally, the biggest disk (disk D) on the bottom. After all the preparations are ready, the player has to move all the disks to the right peg (peg C) with several rules: move only one disk at a time, a larger disk may not be placed on top of a smaller disk, and all disks (except the one being moved) must be on a peg. To find out the minimum number of moves possible (mn) when the number of disks (𝑛) 
is t is three or four, I used an online simulation—https://haubergs.com/hanoi—that was available for the public. After trying a few times, I was able to figure out that the minimum number of movements possible when \(n=3,m_3\ is\ 7,and\ when\ n\ = 4,\ m_4is\ 15.\)​​​​​​​​​​​​​​ //insert image // Figure 1.1: Minimum number of moves when 𝑛 = 3 // //insert image // Figure 1.2: Minimum number of moves when 𝑛 = 4 After proceeding with a simulation, I created a data table of the number of disks and minimum moves.

image1.jpg

Fig 2: The data table of minimum moves when n = 1, 2, 3, and 4 If I assume the minimum moves when \(n=5\) by looking at the difference between \(m_4\) and, \(m_3\), it would be 23\((m_4+m_4-m_3)\). However, if check it with the online simulation, turns out that the actual \(m _5\) is 31. // //insert image // Fig 1.3: Minimum number of moves when 𝑛 = 5 Since the approach using arithmetic sequence has failed, I determined to find out whether this data is arithmetic or not. If this data is an arithmetic sequence, there must be a common difference (d) between two consecutive terms. Therefore, it is possible to state the terms like this: \(m_1=1\) \(m_2=1+d\) \(m_3=1+2d\) \(m_4=1+3d\) If we subtract two consecutive terms, \(m_4-m_3=d\) \(m_3-m_2=d\) It is possible to find out that the positive integer between two consecutive terms should be the same (d). Since we know that the common difference exists, we can test if it really is a “common” difference. \(m_4-m_3=d_3\) \(m_3-m_2=d_2\) \(m_4-m_3=m_3-m_2\) \(15-7\neq7-3\) \(8\neq4\) \(d_3\neq d_2\) \(d\neq d\) It turns out that the ‘common’ difference is different from two consecutive terms, which concludes that the minimum moves in the ToH are not an arithmetic sequence. After that, checking whether the sequence is geometric or not was important. If ToH is a geometric sequence, it should be a ‘common’ ratio (r). Therefore, we can write each term like this: \(m_1=m_1r^0\) \(m_2=m_1r^1\) \(m_3=m_1r^2\) \(m_4=m_1r^3\) Since the value from\(\frac{m_n}{m_n-1}\) should be the r for every term, we can state like this, assuming that k and I are randomly chosen positive integers: \(\frac{m_k}{m_{k-1}}=\frac{m_i}{m_{i-1}}\) If substitute the values into the correct position, \(\frac{m_4}{m_3}=\frac{m_2}{m_1}\) \(\frac{15}{7}\neq\frac{3}{1}\) \(2.14\neq3\) Therefore, we can conclude that ToH is neither arithmetic nor geometric. After confirming that the ToH is not based on arithmetic and geometric sequence, I tried to approach it in a different way. I focused on the number of moves needed for the largest disk, D, to move to peg C \(C(ml_n)\)and the number of moves needed for the rest of the smaller disks to move to peg C \(C(mS_n)\) when n is 1, 2,3, and 4, which is described in the table below.

image2.jpg

Fig 3: The data table \(mL_n\) and \(mS_n\) when =1,2,3, and 4​​​​​​​​​​​​​​ When finding this data, I noticed that for all n (ℤ+), I discovered a pattern in the data. For example, when n=4, to move 3 small disks to peg B, the moves needed are 4, as written in the data table. Then, the minimum number of moves needed to send disk D to peg C is 1. This also means that we only have to move three smaller disks to peg C to complete the puzzle. Therefore, we will have to add one more time to the minimum moves needed when n=4. And this pattern gives an equation of \(m_4=m_3+1+m_3\) ​​​​​​​\(=2m_3+1\) \(m_n=2m_{n-1}+1\) To determine whether this equation works when n=2, 3, 4, and 5, I have tested all of them. \(m_2=2m_1+1\)         \(m_3=2m_2+1\)          \(m_4=2m_3+1\)          \(m_5=2m_4+1\)​​​​​​​​​​​​​​       \(=2+1\)                    \(=6+1\)                     \(=30+1\)                   \(=30+1\) \(m_2=3\)                    \(m_3=7\)                     \(m_4=15\)                   \(m_5=31\) As written above, the equation does work. However, since this equation requires that term when finding the nth term, it can be distributed as the recursive formula. A𝑛−1recursive formula, according to the lumen, “is a formula that defines each sequence term using the preceding term(s). Recursive formulas must always state the initial term, or terms, of the sequence.” Therefore, I will have to find an explicit formula that does not depend on the preceding term(s). The diagram below explains the pattern (different from the recursive formula) between \(m_n\ and\ m_{n-1}(d_n)\)​​​​​​​

image3.png

The diagram I have drawn explains that the difference between  \(m_n \ and\ m_{n-1}\)  increases as increases by a factor of 2. For example, d​​​​​​​3 is 4. This is because it was increased by a factor of 2 from. 𝑑2, which is 2. Then, 𝑑3 gets doubled, making it to 𝑑4​​​​​​​. By concluding the information I found, I could come up with a sequence written below (I derived this equation even though I could’ve used the one that I got earlier because. This makes it easier to find an explicit equation). \(m_n=m_{n-1}+(2^{n-1})\) To prove that this equation works, I calculated 𝑚 𝑛 ​from \(n=2\ to \ n=5\), which also has​​​​​​ been proven by the online simulator (consider 𝑚1 as 20 since 𝑚0 does not exist).  \(m_2=m_1+(2^1)\)          \(m_3=m_2+(2^2)\)           \(m_4=m_3+(2^3)\)          \(m_5=m_4+(2^4)\)​​​​​​​ \(=1+2\)                             \(=3+4\)                         \(=7+8\)                       \(=15+16\) \(m_2=3\)                        \(m_3=7\)                        \(m_4=15\)                      \(m_5=31\) Our next step is to come up with an explicit formula since we can’t rely on the (𝑛 − 1) term every single time. First, let’s list all of 𝑚𝑛 using a recursive equation obtained above. \(m_1=2^0\) \(m_2=m_1+2^1\) \(m_3=m_2+2^2\) \(m_4=m_3+2^3\) \(\cdot\\ \cdot\\ \cdot\) \(m_{n-1}=m_{n-2}+2^{n-2}\) \(m_n=m_{n-1}+2^{n-1}\) Adding all of these terms would make this: \(\left(\sum\limits_{k=1}^{n}m_k\right)-\left(\sum\limits_{k=1}^{n-1}m_k\right)=\sum\limits_{k=1}^{n}2^{k-1}\) \(m_n=\sum\limits_{k=1}^{n}2^{k-1}\)​​​​​​​ \(=\frac{1\left(2^n-1\right)}{2-1}\) \(m_n=2^n-1\)​​​​​​​ According to my calculations, the explicit formula for 𝑚𝑛 is 2𝑛 − 1. I used mathematical induction to prove if this equation works for all n (where n &gt; 0). When n = 1, \(m_1=2^1-1\) \(=1\) When n = k, \(m_k=2^k-1\) Since the recursive equation is valid when n =ℤ+, I can use it for n = k+1. \(m_{k+1}=2(m_k)+1\) \(=2(2^k-1)+1\) \(=\ (2^{k+1}\ -\ 2)\ +\ 1\) \(2^{k+1}\ -1\ =\ 2^{k+1}\ -\ 1 \) Therefore, the explicit equation 𝑚𝑛 = 2𝑛 − 1 is correct. Since we have the explicit equation, we can find out the original research question, the minimum moves when there are 64 disks. \(m_n=2^n-1\) \(m_{64}=2^{64-1}\) \(=18446744073709551615\)

Since the ToH that I was dealing with in this essay had only three pegs, I wondered if the solutions would be harder when there were four or more pegs. I personally think that the puzzle would be much easier to solve when there are four pegs since an extra peg will be available to place a disk while solving. As I thought, the solutions were much easier when there were four pegs. The minimum number of moves when n is 1 and 2 does not change, but when n &gt; 2, the moves decreased than the moves required when there were three pegs. For example, when 𝑛 = 3, only 5 moves were required. And when 𝑛 = 4, only 9 moves were required. Therefore, we can conclude that the number of moves required when there are four pegs is less than three pegs. These are the data table of minimum moves when there are four pegs.

image4.jpg

Fig 4.1: Data table of when there are four pege I tried to find the equation for the minimum number of moves when there are 4 pegs, but I failed to do so. I could only find the patterns but couldn’t put that into an equation. The pattern that I have observed is this: The difference between 𝑚2 and 𝑚1 is 2 (I will call 𝑑𝑛 from now when 𝑚𝑛 − 𝑚𝑛−1). Then, 𝑑3 was 2 as well. However, 𝑑4 𝑑5 and 𝑑6 were 4. Moving on,𝑑7 𝑑8 𝑑9 and 𝑑10 was. Moreover, 𝑑11,𝑑12,𝑑13,𝑑14, and 𝑑15 were 16. If I display the pattern using a diagram, it would be:

image5.png

The numbers at the bottom are 𝑚𝑛. The numbers on the curve are differences, and the numbers on the bracket are the number of times the differences. From this, I was able to find out that even though the number of moves decreased, it became much trickier and harder to find both recursive and explicit equations.

There are two distinct types of ToH apart from the one we just explored. One of the types is the “Bicolor” ToH (BToH). BToH has multiple pegs (usually three), but it has pairs of same-sized disks. If both have three pairs, it has three pairs of same-sized disks. The goal of this puzzle is to make

image6.png

Another type of ToH would be the “Magnetic” ToH (MToH). This version of ToH makes puzzles much more sophisticated. The disk used in this version are magnets, red and blue, stuck together, one facing down and one facing up. All the rules are the same, but this time, when each disk moves, it has to be flipped (if red on top, make it blue).

image7.png

The Fibonacci Sequence (usually denoted Fn )is a series of numbers that follow a single𝐹𝑛rule: the next number should be the value of the sum of two numbers before it. The Fibonacci Numbers list can be 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on. The 2 is found by adding the two numbers before it (1+1), and the 3 is found by adding the two numbers before it (1+2). The interesting part of Fibonacci’s Sequence is that when making squares that have lengths correlating to Fibonacci Numbers, a clean and neat spiral will form, as the figure below displays.

image8.png

The equation for the Fibonacci Sequence (or Number) can be written as both recursive and explicit formula, as displayed below. \(\begin{cases}{ \ \ \ \ \ a_1=1\\ \ \ \ \ \ a_2=1\\a_n = a_{n-2}\ +\ a_{n-1}}\end{cases}\)                                        \(F_n=\frac{\left(\frac{1+\sqrt5}{2}\right)^n-\left(\frac{1-\sqrt5}{2}\right)^n}{\sqrt5}\)   Fig 7.1: Recursive Formula of Fn                          Fig 7.2: Explicit Formula of Fn

Mathematics AI SL's Sample Internal Assessment

Tower of Hanoi

Table of content

Exploring ‘the tower of hanoi’

Extension

1) four pegs

2) bicolor and magnetic toh

3) fibonacci sequence