Question Corner and Discussion Area

Generalizing the Towers of Hanoi Problem

I am currently studying the towers of hanoi problem. I know that if you increase the number disks you increase the minimum number of moves (using to find out how many), but what would happen if you:

1: Increased the number of pegs? (e.g., 4 pegs, so you have to move all the discs from Peg 1 to Peg 4)

or

2: Only moved one peg at a time? (ie 1 -> 3 would not be allowed, but 1->2->3 would be)

or

3: Or even a combination of the above? (e.g., 1->2->3->4)

Can anyone come up with any ideas for those? Any predictions or answers would be most gratefully accepted.

Thanks in Advance

David Watts

For example, let f(n) be the minimum number of moves required to move a pile of n disks from one of the outer pegs to the other outer peg (such as from peg 1 to peg 3, or from peg 3 to peg 1). To accomplish a move of n disks from peg 1 to peg 3, the bottom disk will eventually have to move from peg 1 to peg 3. It can't do so in one move, so it must first move from peg 1 to peg 2 and then move from peg 2 to peg 3. Thus the bottom disk must make at least 2 moves.

Before the bottom disk can make its first move (from peg 1 to peg 2), the top n-1 disks must all be on peg 3. It will take f(n-1) moves to get them there. Next, before the bottom disk can move from peg 2 to peg 3, the top n-1 disks must all be moved from peg 3 back to peg 1; this takes another f(n-1) moves. Finally, the top n-1 disks must be moved to peg 3 again, requiring a third sequence of f(n-1) moves. Thus the top n-1 disks must make a total of at least 3f(n-1) moves.

The total number of moves required is therefore f(n) = 3 f(n-1) + 2. This recursion formula can be solved in the same manner described in the discussion of the standard problem, yielding the solution .

Next, you could ask about moving the pile not from one outer peg to the other, but from an outer peg to an inner peg: say from peg 1 to peg 2. Let g(n) denote the number of turns required to do this for a pile of n disks. (By symmetry this is the same as the number of turns required to move the pile from peg 3 to peg 2, but it is not obvious whether or not this is the same as the number of turns required to move the pile from peg 2 to peg 1 or from peg 2 to peg 3.)

At some time the bottom disk must move from peg 1 to peg 2. Before this can happen, the top n-1 disks must have been moved from peg 1 to peg 3; this takes turns. Then the top n-1 disks must be moved from peg 3 to peg 2; this takes g(n-1) turns. Hence we have

(using the formula for the sum of terms in a geometric progression).

Finally, if you do a similar sort of analysis, you'll discover that this does also happen to equal the number of turns required to move the pile from the middle peg to one of the outer ones.

Now on to your first question. The general case is unsolved. It is not known what the minimum number of moves is as a function of the number of disks and number of pegs.

Some parts of the problem are known; for example, if the number of pegs is greater than or equal to the number of disks, it is easy to see that the minimum number of moves is 2n - 1.

For other configurations there are various unproven conjectures. For example, in the case of 4 pegs, it is conjectured (but not known for sure) that the optimum strategy for moving n disks is to first move some of the topmost disks (say the top k disks) to one of the spare pegs; this takes f(k) moves. Then there are 3 pegs available; use the 3-peg strategy to move the remaining n-k pegs to their destination (which takes moves). Finally, move the top k disks into their final destination, which takes f(k) moves.

Therefore, for any choice of k < n, it is possible to move n disks in moves. It is conjectured that, if you take the value of k that requires the least number of moves, this is an optimal strategy, so

It is not known for sure that this is always optimal, though.

If you calculate values of this function f, you obtain

n	1		2		3		4		5		6		7		8		9		10		11
f(n)	1		3		5		9		13		17		25		33		41		49		65
d		2		2		4		4		4		8		8		8		8		16

Of particular interest are the differences between consecutive f(n) terms (shown in the last row of the table): two 2's, then three 4's, then four 8's, then five 16's, etc.

This pattern allows you to find a formula for f(n). To find this formula, it may be easiest to think first of values just before the gap jumps up: at n=1, at n = 1+2=3, at n=1+2+3=6, at n=1+2+3+4=10, etc. If we let g(N) denote f(1+2+. . . +N), then g(N) equals g(N-1) plus N gaps of size each, so

There are various techniques to solve this recursion formula and get an explicit formula for g(N). One way, not the most elegant but useful if you aren't familiar with standard techniques, is to write out

and then split this up as

(there are N lines here, with appearing in each of them for a total of , with appearing in all but one of them for a total of , and so on).

Now rewrite the above as

If you know the formula for the sum of a geometric series, you know that , so we have

This proves that . (There are much shorter ways to get this, but this is probably the most elementary).

Now, to get a formula for f(n), let N be the largest number for which 1+2+· · ·+N is less than or equal to N. Write n = (1+2+· · ·+N)+m; then f(n) differs from f(1+2+· · ·+N) by m gaps of size , so

Now the only task left is to express N and m as functions of n. To do this, use the formula 1+2+· · ·+N = N(N+1)/2; N is the largest integer such that . In other words, it is the largest integer less than or equal to the positive root r of the quadratic equation r(r+1)/2 = n. Use the quadratic formula to express r as a function of n; then N = [r] (greatest integer less than or equal to r), and m = n - (1+2+· · ·+N) = n - N(N+1)/2.

Plugging all that into the formula for f(n) gives

and setting r to be what you find by the quadratic formula gives you f(n) as a function of n.

Now, this is under the assumption that the observed pattern of gaps really does always continue to hold true. To prove that it does, what you need is to go back to the original definition

and prove by induction that the formula for f(n) found above satisfies this equation. It's not an easy task.

Finally, remember that all this is only for the case of 4 pegs, and is only for the strategy described above (moving a chunk of disks first, then moving the remainder using the 3-peg strategy, then moving the chunk back). This strategy is conjectured, but not known, to be optimal. So the above formula for f(n), even after you prove that it matches our definition, is still only conjectured but not known to be the smallest number of moves required in the 4-peg case.

For other numbers of pegs you can perform similar analyses but things become fare more complicated far more quickly. Again, there are conjectures, but the minimal number of moves is not known (except for small numbers of disks where an exhaustive computer search is possible).

As to your question 3 (the 4-peg case where there is the additional constraint of only being able to move to adjacent pegs), I imagine that too would be a very complex situation for which the exact solution is not known. I have not given it much thought, though.

Asked by a student at Oak Park High School on January 17, 1998:

About the Towers of Hanoi . . .

1. It has three pegs(let's name them S, D and A)
2. All the normal rules are the same except...

No moves are allowed from peg S onto peg D, directly (although the moves from D to S are allowed.)

My question is that what's the minimal number of moves can make??

Would you please give me a hand about this problem?

Thank you very much

Let f(n) stand for the minimum number of turns it takes to move a pile of n disks from peg S onto peg D. Let g(n) stand for the minimum number of turns it takes to move a pile of n disks from peg D onto peg S.

To accomplish a move of n disks from peg S to peg D, the bottom peg will eventually have to move from peg S to peg D. It cannot do so directly, so it must first move to peg A then to peg D. Therefore, the bottom disk must make at least 2 moves.

Before the bottom disk can move to peg A, the top n-1 disks must all be moved from peg S to peg D. The minimum number of turns required for this is f(n-1).

Before the bottom disk can move from peg A to peg D, the top n-1 disks must all be moved from peg D back to peg S. The minimum number of turns required for this is g(n-1).

Finally, the top n-1 disks must be moved back to peg D, requiring f(n-1) turns.

Therefore, the total number of moves required to move the pile of n disks is 2 + 2f(n-1) + g(n-1), so we have the recursion formula f(n) = 2 + 2f(n-1) + g(n-1).

If you do a similar analysis for moving a pile of n disks from peg D to peg S, you get the recursion formula g(n) = 2 + 2 g(n-1) + f(n-1).

One way to solve this pair of linked formulas is to let F(n) = f(n) + g(n) = 2 + 2 f(n-1) + g(n-1) + 2 + 2 g(n-1) + f(n-1) = 4 + 3[ f(n-1) + g(n-1) ] = 4 + 3F(n-1). This you solve using the same technique as described above.

Next, let G(n) = f(n)- g(n) = 2 + 2 f(n-1) + g(n-1) - 2 - 2 g(n-1) - f(n-1) = f(n-1) - g(n-1) = G(n-1). Since G(n)=G(n-1) for all n, it follows that G(n) = G(1) = f(1)-g(1) = 2 - 1 = 1.

Finally, you can solve for f(n) and g(n) using the fact that f(n)-g(n) = 1 to write g(n) = f(n)-1, and plug that into f(n)+g(n)=F(n) to get f(n) = (F(n)+1)/2. I'll leave it to you to finish up the argument and solve for F(n).

Go backward to The Four Fours Problem
Go up to Question Corner Index
Go forward to Deductive Geometry in the High-School Curriculum
Switch to text-only version (no graphics)
Access printed version in PostScript format (requires PostScript printer)
Go to University of Toronto Mathematics Network Home Page