Towers of Hanoi

Most Tower of Hanoi games start with a minimum of 3 discs because towers of height 1 and 2 are trivial to solve. The 1 disc problem takes 1 move. For 2 discs, the top disc needs to be moved off the bottom one, then bottom disc is then moved to the final peg, and the top disc is moved a second time and placed on top the bottom disc. It takes 3 moves total to move a 2 disc tower. By the time we have a tower that is 3 discs tall, it takes a minimum of 7 moves to relocate the tower to another peg. Now, as discs are added the tower, the minimum number of moves goes to 15, 31, and 63. Usually it doesn't take too much time to identify the pattern as 1 less than powers of 2. But it's not very meaningful. Let's unpack this a bit more.

Let's consider the tower with 3 discs. We must first move the top two discs before we can move the bottom disc.

Once the bottom disc is moved to the final location, we must move the top two discs again. The minimum number of moves to solve the 2 disc problem is the same whether the discs are being moved from the left peg to the center peg or the center peg to the right peg. But if we know the number of times it took to solve the 2 disc problem, we simply need to double it and add 1 to account for moving the bottom disk from the left peg directly to the right peg in order to solve the 3 disc problem. That is, we have discovered a recursive relationship that says the tower with n discs can be solved by doubling the minimum number of moves for the n – 1 disc problem and adding 1.

This tells us that the solution to the 2 disc problem is double the solution for one disc, plus 1. In other words, 2 + 1 = 3. Using this pattern for the recursive relationship, we can identify a closed form formula for the minimum number of moves.

As we can see, the minimum number of moves turns out to be a sum of powers of 2, or a geometric series. Moreover, each term in the series tells us exactly how many times each disc must be moved in order to achieve the minimal solution. We know that the bottom disc only needs to be moved once. The rest of the discs have to be moved twice so the disc that is second from the bottom must be moved twice. The remaining discs above the one that is second from the bottom must be moved twice as many times as the disc beneath, and so on.

Now, not only do we have a meaningful solution, we also have a conjecture for the formula for the geometric series based on our observations of the numerical pattern before. That is, we appear to have the following:

We can verify this relationship by doubling the sum and taking the difference. Multiplying the terms of a geometric sequence by the common ratio and taking the difference between the original sum and the product is the standard approach for finding the value of the geometric series, or evaluating the sum of terms of a geometric sequence.

Further Pursuits:

Interestingly, if we look at all the possible legal configurations of the discs (we will consider h = 3 discs) and start connecting the configurations that can be reached by making a single move, we generate a "new" pattern. As it turns out, the structure that emerges is the well-known fractal known as the Sierpinski Triangle. The fractal structure can be seen in the self-similarity of the triangles making up each larger triangle.

The Sierpinski Triangle is a subset of Pascal's Triangle - namely, there is a correspondence between all the possible tower configurations that can be reached in one move and the odd numbers in Pascal's Triangle. This reveals the parity of Pascal's Triangle, that is, the evenness or oddness of integers in the triangle. Learn more here.

Speaking of triangles. Did you notice that our triangular numbers are embedded in the third diagonal of Pascal's Triangle?