On The Frame-Stewart Algorithm For The Multi-Peg T
On The Frame-Stewart Algorithm For The Multi-Peg T
On The Frame-Stewart Algorithm For The Multi-Peg T
net/publication/222540218
CITATIONS READS
36 1,177
3 authors, including:
Uroš Milutinović
University of Ljubljana
27 PUBLICATIONS 470 CITATIONS
SEE PROFILE
All content following this page was uploaded by Uroš Milutinović on 18 January 2022.
Abstract
It is proved that seven different approaches to the multi-peg Tower of Hanoi problem
are all equivalent. Among them the classical approaches of Stewart and Frame from
1941 can be found.
1 Introduction
The rest of the paper is organized as follows. In the next section, we introduce
the following functions (here and later n stands for the number of disks, and
p for the number of pegs):
2
an explicit formula
2 Recursive definitions
Let M(n, p) be the minimum number of moves required to solve the Tower of
Hanoi problem with n disks and p pegs.
Only for p ≥ 4 pegs and n ≥ p disks the problem considered is nontrivial, i.e.
it has been proved that M(n, 3) = 2n −1, and that M(n, p) = 2n−1 for n < p.
Therefore, in the trivial case p = 3 or n < p we shall define all the functions
treated here to be defined as M(n, p). For technical reasons it is useful to note
that M(1, 2) = 1. We shall not define M(n, 2) for n ≥ 2.
All five different definitions for recursive calculations of presumed optimal so-
lution will be now given only outside the trivial range, for n, p ∈ ZZ+ satisfying
p ≥ 4 pegs and n ≥ p, taking the values from the trivial range as initial values,
when required. Also, when proving results about these functions and about
explicit formulas, discussed in Sections 4 and 5, some care will be taken about
the trivial range.
The following definition reflects the Frame’s algorithm for the multi-peg Tower
of Hanoi problem, but it differs from the original definition, since it does not
require partitions of n to be monotone.
where ni ∈ ZZ+ .
3
The original Frame’s definition was essentially the following:
where ni ∈ ZZ+ .
First we have all n disks on the source peg 0. We divide the n − 1 smallest
disks into p − 2 groups of disks of consecutive size. The top n1 smallest disks
are moved from the source peg 0 to the auxiliary peg 1 using all p pegs. The
next n2 smallest disks are moved from the source peg 0 to the auxiliary peg 2
using p − 1 pegs. We continue removing groups of disks from the source peg to
the auxiliary pegs, in each step using one peg less than in the previous one. At
the end the last group of disks is moved from the source peg 0 to the auxiliary
peg p − 2 using the remaining 3 admissible pegs. The last (n-th) disk is then
moved from the source peg 0 to the destination peg p − 1. After that we move
all groups of disks to the destination peg, taking them in the reverse order.
where n1 , n2 ∈ ZZ+ .
First all n disks are on the source peg 0. We divide the disks into two groups,
the first consisting of the smallest n1 disks and the second consisting of the
remaining n − n1 disks. The top n1 disks are moved from the source peg 0
to the auxiliary peg 1 using all p pegs. The remaining n − n1 disks are then
moved from the source peg 0 to the destination peg p − 1 using p − 1 pegs
(all of them but peg 1). Finally, disks from peg 1 are moved to the destination
peg p − 1 using all p pegs.
By simple examples it can be show that S(n, p) does not have a monotone
counterpart (i.e. it gives a different function). For example, the minimum of
4
.1
..
n1
n1.+1
..
n1+n .. 2
.
n1+n2+...+np-3+1
.
..
n1+n2+...+np-2
n
0 1 2 ... p-2 p-1
n1.+1
..
n1+n. 2
..
n1+n2+...+np-3+1
.
.. .1
n1+n2+...+np-2 ..
n n1
0 1 2 ... p-2 p-1
n1+n. 2+1
..
n1+n2+...+np-3+1
.. n1+1
. .1 .
n1+n2+...+np-2 .. ..
n n1 n1+n2
0 1 2 ... p-2 p-1
n1+1 n1+n2+...+np-3+1
.1 .
.. ..
n n1 n1+n2 n1+n2+...+np-2
0 1 2 ... p-2 p-1
n1+1 n1+n2+...+np-3+1
.1 . .
.. .. ..
n1 n1+n2 n1+n2+...+np-2 n
0 1 2 ... p-2 p-1
.1
..
n1
n1.+1
..
n1+n2
.
..
n1+n2+...+np-3+1
.
..
n1+n2+...+np-2
n
0 1 2 ... p-2 p-1
5
.1
..
n1-1
n1
n1+1
.
..
n-1
n
0 1 2 ... p-2 p-1
n1+1 .1
.
.. ..
n-1 n1-1
n n1
0 1 2 ... p-2 p-1
.1 n1+1
.
.. ..
n1-1 n-1
n1 n
0 1 2 ... p-2 p-1
.1
..
n1-1
n1
n1+1
...
n-1
n
0 1 2 ... p-2 p-1
n1 + · · · + np−2 = n} ∪ · · · ∪
′ ′
{2A (n1 , p) + A (n2 , p − 1) | n1 + n2 = n},
where ni ∈ ZZ+ .
6
where ni ∈ ZZ+ .
3 Proof of A′ = F ′ = S
We first state the following two lemmas on the function A′ (n, p). Even if the
first one is more or less obvious (from the fact that A′ (n, p) ≥ M(n, p) ≥ 2n−1)
and the second deals basically only with the trivial cases, we include their
formal proofs, the reason being that several “obvious facts” related to the
Tower of Hanoi problem turned out to be false.
PROOF. For n < p the claim holds by the definition of A′ (n, p). For p = 3
and n ≥ 3 we have A′ (n, 3) = 2n − 1 ≥ 2n − 1. Finally, for p ≥ 4 and n ≥ p
we have
7
If n = 2 then 2 = n = n1 +n2 +· · ·+np−i+1 ≥ p−i+1. Thus p−i ≤ 1 and as on
the other hand we have p − i ≥ 1 it follows that p − i = 1. Then n1 = n2 = 1.
Therefore one only has to show that A′ (2, p) ≤ 2A′ (1, p) + A′ (1, p − 1), which
is indeed the case (3 ≤ 2 · 1 + 1).
2A′ (n1 , p) + 2A′ (n2 , p − 1) + · · · + 2A′ (np−i , i + 1) + A′ (np−i+1 , i)
≥ 2A′ (n1 , p) + A′ (n − n1 , p − 1) .
Therefore, our claim will be proved by showing that 2A′ (n1 , p)+A′(n−n1 , p−1)
≥ A′ (n, p). By Lemma 3.1 we have
A′ (4, 4) = S(4, 4) = 9 .
Assume now that the induction hypothesis is true for all m with 4 ≤ m < n.
Let p be an arbitrary integer satisfying 4 ≤ p ≤ n.
The induction hypothesis implies that for all n1 , n2 ∈ ZZ+ for which n1 +n2 = n
we have
Thus, the set by which we define S(n, p) (as its minimum) is a subset of the set
by which we define A′ (n, p) (as its minimum). It follows that A′ (n, p) ≤ S(n, p).
It remains to prove that A′ (n, p) ≥ S(n, p). If for some n1 and n2 with n1 +n2 =
n we have A′ (n, p) = 2A′ (n1 , p) + A′(n2 , p − 1), then we are done, since in this
8
case A′ (n, p) is in the set of which S(n, p) is the minimum. Suppose therefore
that
Proposition 3.4 For any n ≥ 1 and any p ≥ 3 we have A′ (n, p) = F ′ (n, p).
Assume now that F ′ (m, p) = A′ (m, p) for all m with 4 ≤ m < n. The set
by which we define F ′ (n, p) (as its minimum) is a subset of the set by which
we define A′ (n, p) (as its minimum), because for all n1 , . . . , np−2 for which
n1 + · · · + np−2 + 1 = n we have
9
Now, how far can this procedure be executed? We distinguish two cases.
Note that in the above computation the change of variables in the second
equality is possible since all the values of A′ (1, p − r), . . . , A′ (1, i) as well of
A′ (1, p − r − 1), . . . , A′ (1, i − 1) are equal 1 and i − 1 ≥ 2. Thus we have a
contradiction which shows that this case is not possible.
Now we have
4 Explicit formulas
Explicit formulas we are going to discuss in this section had appeared already
in Frame [6], but have been treated rather heuristically, and — which seems to
be the major deficiency of Frame’s approach — they appeared as statements
10
about M(n, p). Therefore, we believe it is a necessity to give an independent
treatment of them, and using only their properties as well as properties of
A′ , F ′ , S, to prove they really represent these functions (that shall be done in
the following section — and it will turn out to be rather nontrivial).
where s is the largest integer for which the last term on the right side is positive,
i.e. ( )
+ (p − 3 + k)!
s = max k ∈ ZZ | n − >0 .
(p − 2)!(k − 1)!
X(1, p) is defined as
X(1, p) = 1 .
where ( ! )
p−3+k
+
s = max k ∈ ZZ | n − >0 .
p−2
x(x + 1) · · · (x + p − 4)(x + p − 3)
hp (x) =
(p − 2)!
gp = h−1
p
11
which are strictly increasing on nonnegative reals as well.
where gp = h−1
p .
Lemma 4.4 The number s from Definition 4.1 (for n ≥ 2) can be written as
s = fp (n) − 1 .
PROOF. Obviously
n o
s = max k ∈ ZZ+ | n − hp (k) > 0 .
Case 1. fp (n − 1) = fp (n).
12
Case 2. fp (n − 1) 6= fp (n).
5 Proof of X = S
13
Theorem 5.1 For all p ≥ 3, n ≥ 1, it holds true that
X(n, p) = S(n, p) .
PROOF. We shall prove the claim inductively, together with the following
statement:
for p ≥ 4, and k ≥ 2.
Note that hp (k) − hp (k − 1) = hp−1 (k) — what we have here are binomial
coefficients in disguise!
hp (k) + 1 ≤ n ≤ hp (k + 1) ,
for some k ≥ 2. Our inductive assumption is that S(m, p) = X(m, p) for all
m, 1 ≤ m < n, and that S(hp (k), p) = 2S(hp (k − 1), p) + S(hp−1 (k), p − 1).
Then fp (n) = k + 1, fp (hp (k)) = k, and fp (ℓ) ≥ k + 2, for all ℓ > hp (k + 1).
If n1 > hp (k), then fp (n1 ) > k (in fact fp (n1 ) = k + 1), and therefore
14
If n1 ≤ hp (k − 1), then
Thus, since these three cases cover all the possibilities, it follows that S(n, p) ≥
X(n, p). Also, if some n1 satisfies 2S(n1 , p) + S(n − n1 , p − 1) = X(n, p), it
means that S(n, p) = X(n, p) = 2S(n1 , p) + S(n − n1 , p − 1).
we get 3
15
S(hp (k) + 2, p) = X(hp (k) + 2, p)
= 2S(hp (k − 1) + 2, p) + S(hp (k) − hp (k − 1), p − 1) ,
..
.
S(m, p) = X(m, p) = 2S(hp (k), p) + S(hp (k) − hp (k − 1), p − 1) ,
Hence, it remains to fulfill the inductive step in the remaining case when n
satisfies m < n ≤ hp (k + 1). “Inductive proof” now means that inductively
we prove S(t, p) = X(t, p) = 2S(hp (k), p) + S(t − hp (k)) for all t satisfying
m ≤ t ≤ hp (k + 1). Note that by the choice of m that is true for t = m.
Let n satisfies m < n ≤ hp (k + 1) and let the assumption hold true for n − 1.
Now we have
thus finishing also the inductive proof of the additional claim, introduced at
the beginning of the proof. 2
Finally, we are able to show that the original Frame’s function F , as well as
our function A, both coincide with all the rest.
16
PROOF. It means 2fp (n)−1 ≤ 2fp−1 (n)−1 , hence is equivalent to fp (n) ≤
fp−1 (n), which is easily seen to be true. 2
Proposition 6.3 For any n ≥ 1 and any p ≥ 3 we have F ′ (n, p) = F (n, p).
Obviously, F ′ (n, p) ≤ F (n, p), since more partitions are taken into account on
the left hand side.
F ′ (n, p) =
2 F (n1 , p) + · · · + F (ni−1 , p − i + 2) +
F (ni , p − i + 1) + F (ni+1 , p − i) + · · · +1 =
2 X(n1 , p) + · · · + X(ni−1 , p − i + 2) +
X(ni , p − i + 1) + X(ni+1 , p − i) + · · · +1 ≥
2 X(n1 , p) + · · · + X(ni−1 , p − i + 2) +
17
X(ni+1 , p − i + 1) + X(ni , p − i) + · · · +1 ≥
2 F (n1 , p) + · · · + F (ni−1 , p − i + 2) +
F (ni+1 , p − i + 1) + F (ni , p − i) + · · · +1 .
After finitely many repetitions of this procedure, we get that F ′ (n, p) is at least
as large as one of the defining sums for F (n, p), hence F ′ (n, p) ≥ F (n, p). 2
Proposition 6.4 For any n ≥ 1 and any p ≥ 3 we have A′ (n, p) = A(n, p).
PROOF. The trivial range is once again trivial. In the nontrivial range we
have A′ (n, p) ≤ A(n, p), since the set defining the right hand side is a subset
of the set defining the left hand side. Then, we have A(n, p) ≤ F (n, p), for the
same reason, and we already know that A′ (n, p) = F (n, p). 2
Acknowledgments
We wish to thank A.A.K. Majumdar for several discussions on the topic of the
Tower of Hanoi and the referees for their careful reading of our manuscript.
References
[1] A. Brousseau, Tower of Hanoi with more pegs, J. Recreational Math. 8 (1975–
76) 169–178.
[2] N. Claus (= E. Lucas), La Tour d’Hanoi, Jeu de calcul, Science et Nature 1(8)
(1884) 127–128.
[3] P. Cull and E.F. Ecklund Jr., On the Towers of Hanoi and generalized Towers
of Hanoi problems, Congress. Numer. 35 (1982) 229–238.
[4] H.E. Dudeney, The Canterbury Puzzles (and Other Curious Problems, E.P.
Dutton, New York, 1908.
18
[5] O. Dunkel, Editorial note concerning advanced problem 3918, Amer. Math.
Monthly 48 (1941) 219.
[6] J.S. Frame, Solution to advanced problem 3918, Amer. Math. Monthly 48 (1941)
216–217.
[7] A.M. Hinz, An iterative algorithm for the Tower of Hanoi with four pegs,
Computing 42 (1989) 133–140.
[8] A.M. Hinz, Shortest paths between regular states of the Tower of Hanoi, Inform.
Sci. 63 (1992) 173–181.
[10] D.G. Poole, The towers and triangles of professor Claus (or, Pascal knows
Hanoi), Math. Magazine 67 (1994) 323–344.
[11] T. Roth, The Tower of Brahma revisited, J. Recreational Math. 7 (1974) 116–
119.
[12] B.M. Stewart, Solution to advanced problem 3918, Amer. Math. Monthly 48
(1941) 217–219.
[13] P.K. Stockmeyer, Variations on the four-post Tower of Hanoi puzzle, Congress.
Numer. 102 (1994) 3–12.
[14] P.K. Stockmeyer, The Tower of Hanoi: a historical survey and bibliography,
manuscript, September 1997.
[15] D. Wood, The Towers of Brahma and Hanoi revisited, J. Recreational Math.
14 (1981–82) 17–24.
19