Jessica Waggener-
Counting Problems

TOWER OF HANOI

How many moves do you need to move 50 disks from one peg to another? Rules: There are three pegs. You can only move one disk at a time. You are not allowed to place a larger disk on top of a smaller disk.

This was a fun problem. I've seen this puzzle several times before, but never taken the time to solve it. It was rewarding to conquer it!

I began with smaller towers and worked my way up. Figuring out how many steps it takes to get a particular disc off the tower and back onto the right place just took trial and error with manipulating the slips of paper I was using. I don't know exactly why it takes 8 moves to get down to the 4th disc (for example), but I was able to develop a pattern for how many moves are required and I built on that. At first, I was just counting how many total moves it took for different towers.
 

number of disks
total number of moves
1
1
2
3
3
7
4
15
5
31
Then, I tried to dissect the process of moving one tower, specifically the tower with 5 discs. To dissect it, I kept track of what move I was on when I finally got the nth disc off the original tower or onto the final tower (in place).
 
To get: 1 off 2 off  3 off 4 off 5 off/on  4 on 3 on 2 on  1 on
cumulative # moves 1 2  4 8 16 24 28 30 31 
This didn't give me any great insight at first, so then I tried to count the number of moves between each step.
 
To get: 1 off 2 off  3 off 4 off 5 off/on  4 on 3 on 2 on  1 on
cumulative # moves 1 2  4 8 16 24 28 30 31 
# moves at step 1 1  2 4 8 8 4 2 1 
Ah, now we're beginning to see a pattern. Let's look now at the terms of the sum for different numbers of discs.
 
Number of discs
Terms in Sum
Total number of moves
1
1
1
2
1 + 1 + 1
3
3
1 + 1 + 2 + 2 + 1
7
4
1 + 1 + 2 + 4 + 4 + 2 + 1
15
5
1 + 1 + 2 + 4 + 8 + 8 + 4 + 2 + 1
31
6
1 + 2 + 4 + 8 + 16 + 16 + 8 + 4 + 2 + 1
63
Now, consider this same table in terms of 2n.
 
Number of discs
Terms of Sum
1
1
2
1 + 20 + 20
3
1 + 20 + 21 + 21 + 20
4
1 + 20 + 21 + 22 + 22 + 21 + 20
5
1 + 20 + 21 + 22 + 23 + 23 + 22 + 21 + 20
6
1 + 20 + 21 + 22 + 23 + 24 + 24 + 23 + 22 + 21 + 20
From this, I could describe the pattern of summation as:
(TH)n = 1 + 20 + 21 + 22 + 23 + . . . + 2n-3 + 2n-2 + 2n-2 + 2n-3 + . . . 23 + 22 + 21 + 20

But this is a very cumbersome formula. Notice, however that there are always two appearances of every term. So, we can simplify somewhat by expressing 2x + 2x as 2*2x or 2x+1. This gives us a new summation seqence:

(TH)n = 20 + 21 + 22 + 23 + . . . + 2n-2 + 2n-1

Before continuing, let's verify this formula with a few known sums:
 

Number of Disks
Known Sum
Formula Value:
(TH)n = 20 + 21 + 22 + 23 + . . . + 2n-2 + 2n-1
Equal/Unequal
1
1
20 = 1
Equal
2
3
20 + 21 = 3
Equal
3
7
20 + 21 + 22 = 7
Equal
4
15
20 + 21 + 22 + 23 = 15
Equal
Here, we can easily see the recursive formula: (TH)n = (TH)n-1 + 2n-1

At this point, I was still playing with summing particular sequences of numbers using collapsing pairs. I found that for n=6, (TH)6 = 62 +1 = 64 -2 +1 = 26 -2 +1 = 26 -1. So, I made the guess, (TH)n = 2n -1. So, now my question was: Does 2n -1 = 1 + 21 + 22 +23+...+2n-2+ 2n-1? I decided the best approach was to continue trying to collapse my summation. Here I returned to our familiar method of summing terms from opposite ends of the sequence.

(TH)n = 20 + 21 + 22 + 23 + . . . + 2n-2 + 2n-1

Notice that each pair sums to 2n-1. We can use what we've learned before to figure out how many times this sum appears. Counting from zero to n-1 gives us n terms, or n/2 pairs. So, (TH)n = 2n-1(n/2). But this can be simplified as well, because 2n-1/2 is equivalent to 2n-2. So, (TH)n = n*2n-2. Before I continue with this formula, let's verify it for a few known sums:
 

Number of Disks
Known Sum
Formula Value [(TH)n = n*2n-2 ]
Equal/ Unequal
1
1
1*2-1 =1/2
Unequal
2
3
2*20 = 2
Unequal
3
7
2*21 = 4
Unequal
I'm not sure what went wrong, but let's try a slightly different collapsing pattern. Keep the 20 alone and sum the rest as usual. Then each pair sums to 2n. Now there should be (n-1)/2 pairs of this value.
(TH)n = 20 + 21 + 22 + 23 + . . . + 2n-2 + 2n-1

Now, we should get the formula (TH)n = 20 + 2n(n-1)/2. Again, let's try to verify the results.
 

Number of Disks
Known Sum
Formula Value [(TH)n = 20 + 2n(n-1)/2]
Equal/ Unequal
1
1
1 + 21(0)/2 = 1
Equal
2
3
1 + 22(1/2) = 1 +4/2 = 3
Equal
3
7
1 + 23(2/2) = 9
Unequal
Foiled again.

Let's go back to the guess of (TH)n = 2n -1 and try to verify those values.
 
Number of Disks
Known Sum
Formula Value [(TH)n = 2n -1]
Equal/ Unequal
1
1
21 -1 = 1
Equal
2
3
22 -1 = 3
Equal
3
7
23 -1 = 7
Equal
4
15
24 -1 = 15
Equal
5
31
25 -1 = 31
Equal
So, from computational verification, we have two possible summation formulas:

(TH)n = 20 + 21 + 22 + 23 + . . . + 2n-2 + 2n-1
OR (TH)n = 2n -1

Now, the major question is: Why should they be equivalent? or Where does 2n -1 come from? Let's play around with some numbers here. Let's assume that the two expressions are equivalent:

2n -1 = 20 + 21 + 22 + 23 + . . . + 2n-2 + 2n-1
2n = 1 + 20 + 21 + 22 + 23 + . . . + 2n-2 + 2n-1
2n = 20 + 20 + 21 + 22 + 23 + . . . + 2n-2 + 2n-1
2n = 2(20) + 21 + 22 + 23 + . . . + 2n-2 + 2n-1
2n = 21 + 21 + 22 + 23 + . . . + 2n-2 + 2n-1
2n = 2(21) + 22 + 23 + . . . + 2n-2 + 2n-1
2n = 22 + 22 + 23 + . . . + 2n-2 + 2n-1
2n = 2(22) + 23 + . . . + 2n-2 + 2n-1
...
2n = 2(2n-2) +2n-1
2n = 2n-1 + 2n-1
2n = 2(2n-1)
2n = 2n.
I don't know if this proves anything or not, since we assumed they were equal to begin with.

SUMMARY OF SOLUTIONS:


Return to Problems page