Combinatorics Question (Tower of Hanoi, recursion)?
Imagine a Tower of Hanoi in which you have 3 poles as usual, and n different sizes of disks as usual. However, there is 1 disk of the smallest size, there are 2 disks of the next smallest size...and finally n disks of the largest size. Disks are transferred one by one from one pile to another, but a larger disk can never be placed on top of a smaller one. It is OK to put a disk on top of another of the same size. So for instance, if n = 2, you have on pole 1 one disk of the smallest size on top of two equal-sized larger disks. You move the smallest disk to pole 3, then the first large one to pole 2, the second large one to pole 2 also, and then the smallest to pole 2. Total number of moves is 4.
Let a_n be the number of moves needed to move a tower with n different sizes of disks from pole 1 to pole 2. Fine a recursion for a_n, and then give a formula for a_n.
Please include all steps. Thank you!
- alwbsokLv 78 years agoFavorite Answer
I think it's pretty clear that the optimal strategy (or any optimal strategies, if there are more than one) will involve moving all discs of the same size together. We can prove it inductively though.
Let a_k be the smallest number of moves involved in transferring a tower with all of the k largest disc sizes (i.e. not just k discs, but 1 + 2 + 3 + ... + k discs). For the towers to be in a state in which we may legally move one of the largest discs (of which there are k) to a given destination, the destination pole must contain no discs that are strictly smaller (although it could contain another of the largest discs). The source also cannot have any smaller discs on top of it. Therefore, all of the smaller discs must be moved to the remaining pole.
Thus, any algorithm to move the discs of k largest sizes, must first move the discs of k - 1 largest sizes, which takes at least a_(k - 1) steps. So, in order to get to the stage where the largest discs are being moved, we need at least a_(k - 1) steps. From there, we must move the k largest discs to their destination. This requires k moves. From there, we must remove the discs of k - 1 largest sizes to the destination, on top of the discs of largest size, requiring at least a_(k - 1) steps again. Therefore, we have that:
a_k <= a_(k - 1) + k + a_(k - 1)
= 2a_(k - 1) + k
But, of course, my argument described a recursive algorithm for moving the tower. Simply move top of the tower, move the base, then move the top of the tower on top of it. Thus, we have an algorithm executable in 2a_(k - 1) + k moves, which must mean it is optimal (because it achieves the upper bound), and so:
a_k = 2a_(k - 1) + k
Of course, a_1 = 1, since we cannot move the one smallest disc in 0 moves, but we can in 1.
We have (and have proven) the recursive formula:
a_1 = 1
a_k = 2a_(k - 1) + k
We need to find some kind of closed form for this recursive formula. I suggest we do some tentative expansions of a_1, a_2, ..., keeping simplification to a minimum:
a_1 = 1
a_2 = 2a_1 + 2 = 2 * 1 + 2
a_3 = 2a_2 + 3 = 2(2 * 1 + 2) + 3 = 2^2 * 1 + 2 * 2 + 3
a_4 = 2a_3 + 4 = 2(2^2 * 1 + 2 * 2 + 3) + 4 = 2^3 * 1 + 2^2 * 2 + 2 * 3 + 4
Hopefully the following pattern is clear to you:
a_n = 2^(n - 1) * 1 + 2^(n - 2) * 2 + 2^(n - 3) * 3 + ... + 2^2 * (n - 2) + 2 * (n - 1) + n
= ∑ (i = 1 to n) 2^(n - i) * i
= ∑ (i = 1 to n) 2^(n - i) * ∑ (j = 1 to i) 1 ... (writing i as the sum of i ones)
= ∑ (i = 1 to n) ∑ (j = 1 to i) 2^(n - i)
= ∑ (j = 1 to n) ∑ (i = j to n) 2^(n - i) ... (I'm rearranging the sum here; adding the same terms)
Now ∑ (i = j to n) 2^(n - i) is a geometric series, and we can compute its sum. We know that, given a geometric series with initial term a, common ratio r, and number of terms n, that the sum of the n terms is:
a * (r^n - 1) / (r - 1)
If we consider ∑ (i = j to n) 2^(n - i) backwards (for nothing more than convenience's sake), then it starts with i = n, i.e. 2^(n - n) = 1, and its common ratio is 2, with n - j + 1 terms. Thus:
∑ (i = j to n) 2^(n - i) = 1 * (2^(n - j + 1) - 1) / (2 - 1) = 2^(n - j + 1) - 1
a_n = ∑ (j = 1 to n) ∑ (i = j to n) 2^(n - i)
= ∑ (j = 1 to n) [2^(n - j + 1) - 1]
= ∑ (j = 1 to n) 2^(n - j + 1) - ∑ (j = 1 to n) 1
= ∑ (j = 1 to n) 2^(n - j + 1) - n
We have another geometric series here:
∑ (j = 1 to n) 2^(n - j + 1)
Again, considering it backwards, it begins with j = n, so a = 2^(n - n + 1) = 2, and it has a common ratio r = 2. The number of terms is n, so:
∑ (j = 1 to n) 2^(n - j + 1) = 2 * (2^n - 1) / (2 - 1) = 2(2^n - 1)
a_n = 2(2^n - 1) - n
Notice that we never proved that our formula of ∑ (i = 1 to n) 2^(n - i) * i was actually valid, so we should prove this probable formula using induction. Consider n = 1. Then:
a_1 = 1 = 2(2^1 - 1) - 1
which is true. Suppose it works for some n = k, i.e.
a_k = 2(2^k - 1) - k
We need to prove:
a_(k + 1) = 2(2^(k + 1) - 1) - (k + 1)
But, we have the recursive formula, which tells us:
LHS = a_(k + 1)
= 2a_k + (k + 1)
= 2(2(2^k - 1) - k) + k + 1 ... (using the induction hypothesis)
= 2^(k + 2) - 4 - 2k + k + 1
= 2^(k + 2) - 3 - k
= 2^(k + 2) - 2 - (k + 1)
= 2(2^(k + 1) - 1) - (k + 1)
So, the formula works. Thus, for all n, the minimum number of moves required to move this modified tower of hanoi is:
2(2^n - 1) - n
Hope that helps!