**Question Corner and Discussion Area**

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:Let's start with your second question, where the pegs are lined up in a row and you can only move between adjacent pegs. This can be solved by an inductive argument similar to the usual case.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 3*f*(*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 2*n *- 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 | |||||||||||

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 . . .This problem is similar to case 2 (the easier case) of the generalization asked in the previous question.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 + 2*f*(*n*-1) + *g*(*n*-1), so we have the recursion formula *f*(*n*) = 2 +
2*f*(*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 +
3*F*(*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*).

This part of the site maintained by (No Current Maintainers)

Last updated: April 19, 1999

Original Web Site Creator / Mathematical Content Developer: Philip Spencer

Current Network Coordinator and Contact Person: Joel Chan - mathnet@math.toronto.edu

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