Workshop on the Tower of Hanoi and
Related Problems
September 18 - September 22, 2005
Maribor, Slovenia

The Tower of Hanoi - A Personal (Re)Wiew

Andreas M. Hinz


The past of the Tower of Hanoi can be divided into two parts. Prehistory (phase O) ranged from -2300, when the legendary Fu Xi introduced the binary system, to 1883, the year when the famous puzzle was brought out by Édouard Lucas. History (phase I) then lasted until 1985, when an enervated editor asked for "no more articles on this for a while". The present (phase II), i.e. the remaining time until this workshop, is marked by a serious and thorough mathematical treatment of the subject, and the future (phase III) will be occupied with a number of difficult problems left open after more than four thousand years.
These four temporal phases can also be characterized by the topics they were, are and will be dealing with. Phase O witnessed the emergence of basic concepts like binary numbers, complete induction and the mathematical modelling of puzzles as graphs. Phase I was a period of occupation, in such diverse areas as mathematics, computer science and psychology, with the classical Tower of Hanoi problem posed by Lucas and its relations to the Chinese rings, Gray codes and square-free sequences. Phase II can be summarized as the, sometimes implicit, study of the qualitative and quantitative properties of the Hanoi graphs with the emergence of surprising connections to fractals like the Sierpi\'nski triangle, error-correcting codes, finite automata and some classical number sequences. The questions left open for phase III are mainly concerned with Hanoi graphs corresponding to the Tower of Hanoi with more than three pegs. They involve distances on these graphs, crossing numbers and genera. The approaches to these problems are both analytical and experimental mathematics. Practical applications of these studies include sophisticated psychological test devices and benchmark tasks for computing systems.
As long as the monks in Benares will not have finished their task, the Tower of Hanoi and related problems will keep mathematicians busy as well.


The Tower of Hanoi for Humans

Paul K. Stockmeyer


While the recursive presentation of the unique Tower of Hanoi solution algorithm is very elegant and easy to analyze, it is not easily carried out by humans. The priests who are transferring the 64 discs of pure gold day and night, one move per second, are almost certainly not thinking recursively. I will present three alternative presentations that allow both priests and ordinary people to perform the moves automatically, with little thought. All three were discovered a long time ago, all were rediscovered often, and all are frequently attributed to the wrong person.
With these examples for guidance, I will then develop a definition for "human" algorithm presentations and examine some of the consequences of this definition. (Being iterative rather than recursive is necessary but not sufficient for being a human algorithm presentation.)
In the last part of the talk I will examine possible human algorithm presentations for several popular variations of the original problem. These will include restrictions, such as three-in-a-row and cyclic; generalizations, such as converting a random regular configuration into a perfect configuration; and the presumed minimal solution for the Reve's puzzle.


The Tower of Hanoi

Andreas M. Hinz


The aim of this series of lectures is to introduce into the Tower of Hanoi and offsprings of its mathematical theory. It addresses beginners, but may also attract experts by some not so well-known details.
We begin with the prehistory of the subject with such basic topics as the natural numbers, induction, metric spaces and graphs. This introductory chapter is inspired by the Chinese ring puzzle whose mathematical core is the basis of the Tower of Hanoi task, which is described and solved in Chapter 1. This solution is also associated with square-free sequences. For variants of the problem, however, Hanoi graphs have to be introduced. Their quantitative properties will be discussed in Chapter 2. This includes distances on these graphs and connections to the Sierpi\'nski triangle and some further classical integer sequences. The final chapter is then devoted to higher rank Hanoi graphs which are connected to the Tower of Hanoi with more than three pegs. We will recount here what is known and what is still desired. There is also a discussion of numerical approaches to open questions.
The lecture series is accompanied by exercises and some computer experiments.


On a Question of Leiss Regarding the Hanoi Tower Problem

Dany Azriel , Daniel Berend

 The Tower of Hanoi problem is generalized in such a way that the pegs are located at the vertices of a directed graph G, and moves of disks may be made only along edges of G. Leiss obtained a complete characterization of graphs in which arbitrarily many disks can be moved from the source vertex S to the destination vertex D. Here we consider graphs which do not satisfy this characterization; therefore there is only a finite number of disks which can be handled. Denote by gn the maximal such number as G varies over all such graphs with n vertices and S, D vary over the vertices.
Answering a question of Leiss [1], we prove that gn grows sub-exponentially fast. Moreover, there exists a constant C such that gn Ł Cn[1/2] log2 n for each n. On the other hand, for each e > 0 there exists a constant Ce > 0 such that gn ł Ce n([1/2] -e)log2 n for each n.

References

[1]
E.L. Leiss, Finite Hanoi problems: How many discs can be handled?, Congr. Numer. 44 (1984), 221-229.


Hypercubes are Distance Graphs

Melita Gorše Pihler , Janez Žerovnik


The f-distance between G1 and G2 is
df(G1,G2)= ĺ
 |dG1(u,v)-dG2(fu,fv)|,
(1) where the sum is taken over all (n || 2) unordered pairs u, v of vertices of G1. Of course, if df(G1,G2)=0 then f is an isomorphism and G1 @ G2, while if G1 \ncong G2, then df(G1,G2) > 0 for every one-to-one mapping f. This suggests defining the distance d(G1,G2) between G1 and G2 by
d(G1,G2)= min
 {df (G1,G2)},
(2) where the minimum is taken over all one-to-one mappings f from V(G1) to V(G2). Thus, d(G1,G2)=0 if and only if G1 @ G2. Hence d(G1,G2) can be interpreted as a measure of the similarity of G1 and G2, because the smaller the value of d(G1,G2), the more similar the structure of G1 is to that of G2.
Let S be a set of connected graphs having the same order. Then the distance graph D(S) of S has vertex set S and two vertices G1 and G2 of D(S) are adjacent if and only if d(G1,G2)=1. Further, we say that a graph G is a distance graph if there exists a set S of graphs having fixed order such that D(S) @ G.
It has been recently conjectured [1] that: A graph G is a distance graph if and only if G is bipartite and proved that: every distance graph is bipartite, every even cycle is a distance graph, every tree is a distance graph, the graph K2,n is a distance graph for every positive integer n, etc.
Here we support the conjecture by proving that


Theorem: Every induced subgraph of a hypercube is a distance graph.


Reference
[1] G. Chartrand, G. Kubicki and M. Schultz, Graph similarity and distance in graphs, Aequationes Math. 55 (1998), 129-145.


On Tower Powers of Graphs

Robert E. Jamison , Craig Turner


This talk is based on the 1993 Doctoral Dissertation of my student Craig Turner. Consider any graph G = (V,E) which will be called the peg structure. We do not wish to refer to rings as in the original Tower of Hanoi problem but to a set \mathscrM of marks. The marks are partially ordered and an assignment of the marks to the vertices of G is a position in the order power of G by the \mathscrM. It is not necessary to think of the marks as physical objects. It is not necessary to think of them as being placed in some order on a physical peg which the vertex represents. A position is simply a map a: \mathscrM®V. The set of marks assigned to a vertex v is the stack at that vertex.
The positions are the vertices of the order power. Two positions a and b are adjacent iff a can be obtained from b by moving a mark m from the stack at some vertex v of G to an adjacent vertex w of G such that m is minimal in both these stacks.
When the marks \mathscrM are totally ordered - that is, form an order theoretic tower - then we call this a tower power of G. Notice that the weaker the order of \mathscrM, the more edges there are in the order power. The Tower Power is most restrictive. And the case when \mathscrM is an antichain is least restrictive and gives the usual cartesian (box) product.
In his dissertsation, Craig Turner investigated, among other things, relationships between properties of peg structures and Tower Powers. I will survey some of these results here.


Many Aspects of Sierpinski Graphs

Sandi Klavžar


Sierpinski graphs S(n,k) were introduced in [1], where it is in particular shown that the graph S(n,3), n ł 1, is isomorphic to the graph of the Tower of Hanoi with n disks. This family of graphs has many interesting properties, and the way they are labeled offer many possible applications. In this talk we will briefly survey some of such results. In particular we will mention that (just a slightly modified) Sierpinski graphs form the first nontrivial family of graphs of "fractal" type whose crossing number is known [2]. Moreover, Romik [3] used the Sierpinski labeling and finite automata for several insights into the shortest paths of the Tower of Hanoi graphs.

References

[1]
S. Klavžar and U. Milutinovi?, Graphs S(n,k) and a variant of the Tower of Hanoi problem, Czechoslovak Math. J. 47(122) (1997), 95-104.
[2]
S. Klavžar and B. Mohar, Crossing numbers of Sierpinski-like graphs, J. Graph Theory, in press.
[3]
D. Romik, Shortest paths in the Tower of Hanoi graph and finite automata, manuscript, 2004.


Hanoi Variations

Fred Lunnon


In addition to the obvious recursive method, the Classical Towers of Hanoi problem possesses several direct solution algorithms: in particular, one based on bi-colouring the discs, another based on directing the moves between pins, and a third periodic in respect of the pins with period 3 moves. These solutions in turn suggest a pair of excellent three-pin variations: R. Neale's Rainbow with colours increased from 2 to 3; and D. Knuth's Cyclic with direction limited cyclically to (say) clockwise.
The construction of an analogous colouring algorithm for the Cyclic problem suggests the notion of discs whose colour flips as they move, which in turn leads to a pair of intriguing new variations: Reversi, where the colour of a disc always flips and (as for Classical) differs from that below; and Domino, where it flips but matches below. With three pins, Reversi is easily found to be insoluble; Domino on the other hand, resembling a noticeably gnarlier version of Rainbow, can be (and more or less has been) completely solved.
Undaunted, we press on to consider various solutions for four-pin Reversi, for which an optimal solution cannot currently even be plausibly conjectured. However, one special case in which the bases are also coloured possesses a remarkable optimal periodic solution with period of 8 moves, which proves in addition to be a (very inefficient) solution to another bi-coloured four-pin variation: Checkers, where the colours do not flip, and differ from below. Although not inherently very exciting, the latter puzzle casts some light on the Reve's puzzle (or classical four-pin): the Frame conjecture fails for Checkers. [It is not known whether an optimal solution for Checkers is also an optimal solution for the Reve's: 15 discs is our earliest unresolved case.]
The discussion of these and related puzzles (according to time available) will be enlivened by its author's attempts to illustrate their solution with the assistance or otherwise of an interactive computer program HanoiVar, a Java application which has been designed to facilitate the presentation and exploration of such variations.


Stern's Polynomials

Sandi Klavžar , Uros Milutinovi? , Ciril Petr


Sierpinski graphs S(n,k) were introduced in [4], where it is shown that the graph S(n,3), n ł 1, is isomorphic to the graph of the Tower of Hanoi with n disks. Here we generalize the results of [3] from the Tower of Hanoi graphs to arbitrary S(n,k). Instead in terms of Stern's diatomic sequence, new results are given in terms of Stern's (diatomic) polynomials. Connections with different numeration systems are obtained as well [1,2].

References

[1]
P. Flajolet and L. Ramshaw, A note on Gray code and odd-even merge, SIAM J. Comput. 9 (1980) 142-158.
[2]
C. Heuberger and H. Prodinger, On minimal expansions in redundant number systems: Algorithms and quantitative analysis, Computing 66 (2001) 377-393.
[3]
A. M. Hinz, S. Klavžar, U. Milutinovi?, D. Parisse and C. Petr, Metric properties of the Tower of Hanoi graphs, European J. Combin.  26 (2005) 693-708.
[4]
S. Klavžar and U. Milutinovi?, Graphs S(n,k) and a variant of the Tower of Hanoi problem, Czechoslovak Math. J. 47(122) (1997), 95-104.


On Some Metric Properties of the Sierpinski Graphs S(n,k)

Daniele Parisse


Sierpinski graphs S(n,k), n,k Î \mathbb N, can be interpreted as graphs of a variant of the Tower of Hanoi with k ł 3 pegs and n ł 1 discs. In particular, it has been proved that for k = 3 the graphs S(n,3) are isomorphic to the Hanoi graphs Hn3. In this paper the chromatic number, the diameter, the radius and the center of S(n,k) will be determined. Moreover, an important invariant and a number-theoretical characterization of S(n,k) will be derived. By means of these results the complexity of Problem 1, that is the complexity to get from an arbitrary vertex v Î S(n,k) to the nearest and to the most distant extreme vertex, will be given. For the Hanoi graphs Hn3 some of these results are new.


[1] A. M. Hinz, The Tower of Hanoi, Enseign. Math. (2) 35 (1989) 289-321.
[2] S. Klavžar and U. Milutinovi?, Graphs S(n,k) and a variant of the Tower of Hanoi problem, Czechoslovak Math. J. 47 (122) (1997) 95-104.
[3] D. Parisse, The Tower of Hanoi and the Stern-Brocot Array, Thesis, München, 1997.


Computational Experiments over Multi-peg Tower of Hanoi

Ciril Petr


One of the most challenging open problems in multi-peg Tower of Hanoi is proving the optimality of the algorithm which defines the sequence of moves between two perfect states. Frame [1] and Stewart [5] were first to propose such solutions and there are many equivalent approaches to these solutions [3]. In [2] A. M. Hinz coined the term "presumed minimum solution" to describe proposed solutions.
In all optimal sequences the largest disc is moved exactly on the half of the sequence. The move of the largest disk is possible only if all other disks are placed on the pegs not involved into this move. The presumed minimum solutions are realized only by considering some special superdisc states at the move of the largest disc. Which are the states not considered by presumed minimum solutions, but are also on optimal paths?

References

[1]
J. S. Frame, Solution to advanced problem 3918, Amer. Math. Monthly 48 (1941) 216-217.
[2]
A. M. Hinz, An iterative algorithm for the Tower of Hanoi with four pegs, Computing 42 (1989) 133-140.
[3]
S. Klavžar, U. Milutinovi? and C. Petr, On the Frame-Stewart algorithm for the multi-peg Tower of Hanoi problem, Discrete Appl. Math. 120 (2002) 141-157.
[4]
S. Klavžar, U. Milutinovi? and C. Petr, Hanoi Graphs and Some Classical Numbers, to appear in Expo. Math.
[5]
B. M. Stewart, Solution to advanced problem 3918, Amer. Math. Monthly 48 (1941) 217-219.


On the Generalized Tower of Hanoi Problem: An Introduction to Clusters

Andrey Rukhin


I will present a novel approach to the Tower of Hanoi puzzle: we will consider the concept of a cluster to help analyze the problem. It has been proclaimed that the mathematical structure of the puzzle needs to be fully established before one can make arguments concerning minimal paths with the puzzle. I will present such a structure and, time permitting, I will present some general results concerning minimality within this context.


Identification of Diameter of Configuration Graphs

Daniel Berend , Amir Sapir


Versions of the classical Tower of Hanoi problem evolved in various directions, of which the addition of pegs and avoidance of direct moves between some pairs of pegs are the framework in which we deal. In other words, the pegs are the vertices of some directed graph, and an arc designates the permission to move a disk between the corresponding pegs, along the direction of that arc (henceforth variant graph).
Besides finding solutions to versions, the Tower of Hanoi is a rich source for questions. In some of them, one is clearly led to guess a certain answer, which turns out surprisingly to be incorrect [3]. One such instance is the following:
Question Find a pair of disk arrangements (henceforth configurations) requiring the longest move sequence in order to get from one to the other.
Intuition directs us to believe that such configurations are perfect - all disks are stacked on a single peg. Indeed, for Complete it has been long known that the transition from one perfect configuration to another requires more moves than are required for a transition between any two configurations ([4], [8]). However, this is not the case for the general 4-peg problem. Consider Complete4 and 15 disks. As can be deduced from the expressions in [5], a perfect task requires 129 moves, whereas Korf [6,7] found non-perfect configurations that require 130 moves to reach a perfect configuration.
Representing each configuration by a vertex, and the ability to move from one configuration to the other in a single move by an arc, we form a configuration graph. In graph-theoretic terms, we are interested in finding its diameter Dn, and the vertices which yield it.
In this talk we identify the longest tasks for all the 3-peg versions and for the Cyclich versions, for h ł 4 [2]. For the latter family of versions this result is obtained despite that we cannot determine the exact complexity of the tasks [1], and is of particular interest since, among all strongly connected digraphs on h vertices, Cyclich is the `least connected' (in the sense that the in-degree and out-degree of each vertex is 1) and thus seems a good candidate for being the graph requiring the largest number of moves for transferring a tower of disks.
Let Ri,n be the perfect configuration with n disks on peg i, Ri,n ® Rj,n - the perfect task from peg i to peg j, dij,n - the length (minimal number of moves) of such a task, and put dn = maxi,jdij,n. Obviously, for any variant graph dn Ł Dn. Specifically,
Theorem 1   For any variant graph on 3 vertices:
Dn = dn  ,        n ł 1 .
In the course of proving the theorem, we will identify the pairs of configurations which require the largest number of moves, using a term as an inexistent arc, and considering perfect tasks over inexistent arcs, which will be explained in the talk.
Theorem 1 cannot be extended to 4-peg versions in general, as was mentioned earlier. However, our main result states that in the Cyclich version such an anomaly cannot occur. Moreover, we prove the transition between the two farthest perfect configurations takes more steps than the transition between any other pair of configurations.
Theorem 2 For all Cyclich graphs where h ł 3, and for n ł 1:
Dn = dn = dij,n  ,
where j = (i-1)   mod   h.

References

[1]
D. Berend and A. Sapir. The cyclic multi-peg Tower of Hanoi. ACM Trans. on Algorithms, accepted.
[2]
D. Berend and A. Sapir. The diameter of Hanoi graphs. Inform. Process. Lett., accepted.
[3]
J.-P. Bode and A. M. Hinz. Results and open problems on the Tower of Hanoi. Congr. Numer., 139:113-122, 1999.
[4]
A. M. Hinz. The Tower of Hanoi. Enseign. Math., 35:289-321, 1989.
[5]
S. Klavžar, U. Milutinovi?, and C. Petr. On the Frame-Stewart algorithm for the multi-peg Tower of Hanoi problem. Discrete Applied Math., 120:141-157, 2002.
[6]
R. E. Korf. Best-First frontier search with delayed duplicate detection. Proc. of National Conf. on AI (AAAI-04), pages 650-657, 2004.
[7]
R. E. Korf. Private communication. 2004.
[8]
D. Wood. Adjudicating a Towers of Hanoi contest. Internat. J. Comput. Math., 14:199-207, 1983.


The Complexity of the Cyclic Versions

Daniel Berend , Amir Sapir


Adding pegs and imposing move restrictions between some pairs of pegs are the source of many versions. A straight-forward representation of such a version is by a digraph where a vertex stands for a peg, and an arc - for the permission to move a disk between the corresponding pegs, along the direction of that arc (henceforth variant graph). The number of isomorphically different graphs (and hence versions) grows considerably as the number of vertices grows.
All 3-peg versions are H-exp - that is, require an exponentially fast growing number of moves (as a function of the number of disks n) to transfer a tower of n disks from one peg to another (cf. [4]). The Complete4 requires (somewhat surprisingly) a sub-exponentially fast growing number of moves (cf. [6]) - henceforth H-subexp. Most of the 83 strongly connected digraphs with 4 vertices (that is, the versions on 4-pegs) are H-subexp, and this percentage grows with the increase in the number of vertices h.
In [5], an upper bound of 3n-1 was obtained for the complexity of (moving a tower of n disks from peg 1 to peg 3 in) Cyclic4. It was observed in [6] that this bound is not tight, but the question whether the complexity is exponential as a function of the number of disks was left open. We shall show that the complexity is indeed exponential, provide also upper bounds, and prove it behaves roughly as ln for some l > 1. We indicate how lh may be better estimated for any specific h using (heavy) computer calculations.
Let f ł 0 and denote by b=b(h,f) the maximal length of all legal sequences of moves (starting from any initial configuration) containing no more then f moves of disk 1. Then
Theorem 3  
l ł b+1
b-f
  .
Let Ri,n be the perfect configuration with n disks on peg i, R1,n ® R1+j,n - the perfect task from peg 1 to peg j+1 and aj,n - the length (minimal number of moves) of such a task. Due to symmetry, the length of a minimal solution for moving a tower of disks from a source peg to a destination depends only on the distance between these pegs. Since the diameter of the configuration graph of Cyclich equals ah-1,n ([2]), and the rate of growth of ak,n as a function of n is essentially the same for all 1 Ł k Ł h-1, we shall focus only on a1,n, which, for brevity, will be denoted by an. Setting l = limn ® Ą nÖ{an}, we prove that there is a constant C such that ln-1 Ł an Ł C(l+e)n.
Convergence to l can be accelerated by looking at sequences of solutions where disk 1 makes a minimal number of moves, even at the expense of a longer overall sequence. In the next theorem we utilize consecutive moves of disk 1 (referring to j consecutive moves of disk 1 as a j-peg move) to achieve better upper bounds for l.
Theorem 4   Assume we have an algorithm for the transition R1,n0 ® Rk+1,n0 for 1 Ł k Ł h-1 and some fixed n0 ł 2. Denote by an0,k(1),j the number of j-peg-moves of disk 1 while making this transition. Put M=(an0,k(1),j)k,j=1h-1. Let ln0,h be the largest eigenvalue of M. Then:
lh Ł
n0-1
Ö
 
ln0,h
 
  .
Next we consider the behavior of lh as a function of h.
Theorem 5   Let h ł 3. Then:
(a) lh+1 Ł lh  .
(b) 1+[6/(7(h-1)2)] Ł lh Ł (h-1)[2/(h-2)]  .
 Summary The most important result is proving that Cyclich is H-exp. Further, it is obtained despite that we cannot determine the exact complexity of the tasks [1], and is of particular interest since, among all strongly connected digraphs on h vertices, Cyclich is, in a sense, the `least connected'. If this is so, an upper bound for the complexity of a Cyclich for any specific h can serve as an upper bound for any version with h vertices.

References

[1]
D. Berend and A. Sapir. The cyclic multi-peg Tower of Hanoi. ACM Trans. on Algorithms, accepted.
[2]
D. Berend and A. Sapir. The diameter of Hanoi graphs. Inform. Process. Lett., accepted.
[3]
A. Berman and R. J. Plemmons. "Nonnegative Matrices in the Mathematical Sciences", Classics in Applied Mathematics, volume 9. SIAM, Philadelphia, 1994.
[4]
A. Sapir. The Tower of Hanoi with forbidden moves. Comput. J., 47(1):20-24, 2004.
[5]
R. S. Scorer, P. M. Grundy, and C. A. B. Smith. Some binary games. Math. Gazette, 280:96-103, 1944.
[6]
P. K. Stockmeyer. Variations on the Four-Post Tower of Hanoi puzzle. Congr. Numer., 102:3-12, 1994.


Central Mean as a Threshold for Augmentation of Decision-Making Committees

Daniel Berend , Luba Sapir


There is a variety of situations where a group of experts is required to select one of two alternatives, of which exactly one is correct. The experts, which may be humans or not (say, computers or algorithms), share a common preference - to identify the correct alternative. This model is known as the dichotomous choice model, and goes back as far as Condorcet (1785). Its applications are relevant to a wide variety of areas.
Let n be the size of the group, and denote by pi,  1 Ł i Ł n, the probabilities of the experts to make the right choice. We assume that pi ł 1/2 for 1 Ł i Ł n, and that the experts are independent in their choices. A decision rule is a rule for translating the individual opinions into a group decision. The number of all possible decision rules is 22n. The most well known decision rule is the simple majority rule.
In the study of the dichotomous choice model, we focus on the simple majority rule, used in Condorcet's Jury Theorem. This theorem provides a theoretical basis of public choice and political science theory, and has been a subject of extensive study in recent decades. Condorcet's Jury Theorem states, roughly speaking, that a group utilizing the simple majority rule is more likely to choose correctly as its size increases.
Is the augmentation of the group always an advantage? The answer depends on the interpretation. For a fixed committee and random subcommittees thereof, it is in general correct. However, this is not necessarily the case for fixed subcommittees. We obtain a necessary and sufficient condition for a small augmentation of the decision-making body to be beneficial. This condition is based on a threshold, which turns out to be a certain symmetric polynomial mean (henceforth central mean) of the competence levels of the current committee members, i.e. [(pi)/(1-pi)],  1 Ł i Ł n. An interesting feature of our condition is that it splits the required information into two parts, one depending only on the current group members and the other only on the new candidates. We explore the condition from various points of view, such as
  • a time required for its verification,
  • its connections with well-known means (arithmetic, geometric and harmonic),
  • its intuitive meaning.
In addition, we derive conditions enabling us to know that the augmented committee is better (or worse) than the original one even though we know only the competencies of some of the most (or least) qualified members of the original committee.


Optimality of an Algorithm Solving the k-Relaxed Hanoi Towers Problem

Yefim Dinitz , Shay Solomon


We study the k-Relaxed Hanoi Towers Problem RHTk(n), which was posed by D. Wood in 1981. It differs from the classic problem by a relaxed placement rule: A bigger disk j may be placed above a smaller disk i if their size difference is less than k. The shortest sequence of moves from the standard state of disks [1..n] on peg A to that on peg C, using peg B, is in question. If k is 1, we arrive at the classic problem.
Beneditkis, Berend, and Safro suggested, in 1998, the following sequence of moves Ĺk(n), and for the case k=2, proved its optimality for RHTk(n):
  1. Move disks [1..(n-1)] from A, by the minimum possible number of moves, to any (legal) state on B.
  2. Move disk n from A to C.
  3. Move disks [1..(n-1)] from B to C, by the sequence of moves symmetric to that at stage 1.
The shortest "somehow" move sequence of disks [1..r], from the standard state on peg X to any legal state on peg Y, using peg Z, bk(r), is obvious when r Ł k: move all disks from X to Y one by one. For the general r, the sequence bk(r) was defined, by Beneditkis, Berend, and Safro, recursively:
  • Perform bk(r-k), from X to Z.
  • Move disks [(r-k+1)..r], one by one, from X to Y.
  • Perform bk(r-k), from Z to Y.
We prove optimality of Ĺk(n) for RHTk(n), for the general k.

File translated from TEX by TTH, version 3.70.
On 23 Sep 2005, 17:56.
Main page