Volume 6 Issue 2

Simple Explicit Formulas for the Frame-Stewart Numbers

Sandi Klavžar and Uroš Milutinović

Department of Mathematics, PEF, University of Maribor, Koroska cesta 160, 2000 Maribor Slovenia

{sandi.klavzar, uros.milutinovic}@uni-mb.si

Annals of Combinatorics 6 (2) p.157-167 June, 2002

AMS Subject Classification: 05A10, 11B83

Abstract:

Several different approaches to the multi-peg Tower of Hanoi problem are equivalent. One of them is Stewart's recursive formula

In the present paper we significantly simplify the explicit calculation of the Frame-Stewart's numbers S(n,p) and give a short proof of the domain theorem that describes the set of all pairs

, such that the above minima are achieved at

Keywords: multi-peg Tower of Hanoi problem, Frame-Stewart numbers, recursion

References:

1. J.-P. Bode and A.M. Hinz, Results and open problems on the Tower of Hanoi, In: Proceedings of the Thirtieth Southeastern International Conference on Combinatorics, Graph Theory, and Computing, Boca Raton, FL, 1999, Congr. Numer. 139 (1999) 113–122.

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, On the Towers of Hanoi and generalized Towers of Hanoi problems, Congr. Numer. 35 (1982) 229–238.

4. P. Cull and I. Nelson, Error-correcting codes on the Towers of Hanoi graphs, Discrete Math. 208/209 (1999) 157–175.

5. H.E. Dudeney, The Canterbury Puzzles (and Other Curious Problems), E.P. Dutton, New York, 1908.

6. O. Dunkel, Editorial note concerning advanced problem 3918, Amer. Math. Monthly 48 (1941) 219.

7. J.S. Frame, Solution to advanced problem 3918, Amer. Math. Monthly 48 (1941) 216–217.

8. A.M. Hinz, The Tower of Hanoi, Enseign. Math. 35 (1989) 289–321.

9. A.M. Hinz, The Tower of Hanoi, In: Algebras and Combinatorics, Hong Kong, 1997, Springer, Singapore, 1999, pp. 277–289.

10. A.M. Hinz and A. Schief, The average distance on the Sierpinski gasket, Probab. Theory Related Fields 87 (1990) 129–138.

11. S. Klavzar, U. Milutinovic, and C. Petr, On the Frame-Stewart algorithm for the multi-peg Tower of Hanoi problem, Discrete Appl. Math. 120 (2002) 141–157.

12. A.A.K. Majumdar, The generalized four-peg Tower of Hanoi problem, Optimization 29 (1994) 349–360.

13. A.A.K. Majumdar, Generalized multi-peg Tower of Hanoi problem, J. Austral. Math. Soc. Ser. B 38 (1996) 201–208.

14. G. Pólya and G. Szegö, Problems and Theorems in Analysis II, Theory of Functions, Zeros, Polynomials, Determinants, Number Theory, Geometry, reprint of the 1976 English translation, Classics in Mathematics, Springer-Verlag, Berlin, 1998.

15. B.M. Stewart, Solution to advanced problem 3918, Amer. Math. Monthly 48 (1941) 217– 219.

16. M. Szegedy, In how many steps the k peg version of the Towers of Hanoi Game can be solved?, In: STACS 99, Trier, Lecture Notes in Computer Science 1563, Springer, Berlin, 1999, pp. 356–361.

Get the PDF file of this abstract. | Get the Full Text of this paper.

This site is maintained by Bill Chen. If you have any suggestions or anything to contribute, please contact me at