Skip to main content
Springer Nature Link
Log in

Santa Claus’ Towers of Hanoi

  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

Two new variants of the Towers of Hanoi problem are proposed. In both variations, one is allowed to put a bigger disk directly on the top of a smaller one under some restrictions. We give procedures to solve these two versions, and prove the optimality of our procedures. Our solution also resolves a problem, which is similar to one of our versions, proposed by D. Wood in 1981.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
€32.70 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (France)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Atkinson, M. D.: The cyclic towers of Hanoi. Inf. Process. Lett. 13(3), 118–119 (1981)

    Google Scholar 

  • Chen, X., Shen, J., On the Frame–Stewart conjecture about the Towers of Hanoi. SIAM J. Comput. 33(3), 584–589 (2004)

    Google Scholar 

  • Claus, N., (= Lucas, E.): La Tour d Hanoi. Jeu de calcul. Sci. Nat. 1(8), 127–128 (1884)

  • Dinitz, Y., Solomon, S.: Optimality of an algorithm solving the Bottleneck tower of Hanoi problem, a manucript, 2006

  • Frame, J. S.: Solution to advanced problem 3918. Am. Math. Mon. 48, 216–217 (1941)

    Google Scholar 

  • Klavžar, S., Milutinović, U., Petr, C.: On the Frame–Stewart algorithm for the multi-peg Tower of Hanoi problem. Discrete Appl. Math. 120(1–3), 141–157 (2002)

    Google Scholar 

  • Klein, C. S., Minsker, S.: The super Towers of Hanoi problem: large rings on small rings. Discrete Math. 114(1–3), 283–295 (1993)

    Google Scholar 

  • Poole, D.: The Bottleneck Towers of Hanoi problem. J. Recreat. Math. 24(3), 203–207 (1992)

    Google Scholar 

  • Stewart, B. M.: Advanced problem 3918. Am. Math. Mon. 46, 363 (1939)

    Google Scholar 

  • Stewart, B. M.: Solution to advanced problem 3918. Am. Math. Mon. 48, 217–219 (1941)

    Google Scholar 

  • Stockmeyer, P. K.: The Tower of Hanoi: A Historical Survey and Bibliography, manuscript available at http://www.cs.wm.edu/~pkstoc/biblio.ps, 2001

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

  • Wood, D.: Towers of Brahma and Hanoi Revisited. J. Recreat. Math. 14, 17–24 (1981)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Rutgers University, Piscataway, NJ, USA

    Xiaomin Chen, Bin Tian & Lei Wang

Authors
  1. Xiaomin Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Bin Tian
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Lei Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Xiaomin Chen.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Chen, X., Tian, B. & Wang, L. Santa Claus’ Towers of Hanoi. Graphs and Combinatorics 23 (Suppl 1), 153–167 (2007). https://doi.org/10.1007/s00373-007-0705-4

Download citation

  • Received:

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-007-0705-4

Keywords

Search

Navigation