Selenite Towers Move Faster Than Hanoï Towers, But Still Require Exponential Time

Author Jérémy Barbay



PDF
Thumbnail PDF

File

LIPIcs.FUN.2016.5.pdf
  • Filesize: 0.62 MB
  • 20 pages

Document Identifiers

Author Details

Jérémy Barbay

Cite AsGet BibTex

Jérémy Barbay. Selenite Towers Move Faster Than Hanoï Towers, But Still Require Exponential Time. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.FUN.2016.5

Abstract

The Hanoi Tower problem is a classic exercise in recursive programming: the solution has a simple recursive definition, and its complexity and the matching lower bound correspond to the solution of a simple recursive function (the solution is so simple that most students memorize it and regurgitate it at exams without truly understanding it). We describe how some minor change in the rules of the Hanoi Tower yields various increases of difficulty in the solution, so that to require a deeper mastery of recursion than the classical Hanoi Tower problem. In particular, we analyze the Selenite Tower problem, where just changing the insertion and extraction positions from the top to the middle of the tower results in a surprising increase in the intricacy of the solution: such a tower of n disks can be optimally moved in 3^(n/2) moves for n even (i.e. less than a Hanoi Tower of same height), via 5 recursive functions (or, equivalently, one recursion function with five states following three distinct patterns).
Keywords
  • Brähma tower
  • Disk Pile
  • Hanoi Tower
  • Levitating Tower
  • Recursivity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. J.-P. Allouche and F. Dress. Tours de Hanoï et automates. RAIRO, Informatique Théorique et applications, 24(1):1-15, 1990. Google Scholar
  2. M.D. Atkinson. The cyclic towers of Hanoï. Information Processing Letters (IPL), 13(118-119), 1981. Google Scholar
  3. W. R. Ball. Mathematical Recreations and Essays. McMillan, London, 1892. Google Scholar
  4. J. S. Frame and B. M. Stewart. Solution of problem no 3918. American Mathematics Monthly (AMM), 48:216-219, 1941. Google Scholar
  5. Édouard Lucas. La tour d'Hanoï, véritable casse-tête annamite. In a puzzle game., Amiens, 1883. Jeu rapporté du Tonkin par le professeur N.Claus (De Siam). Google Scholar
  6. Édouard Lucas. Récréations Mathématiques, volume II. Gauthers-Villars, Paris, quai des Augustins, 55, 1883. Google Scholar
  7. D. Wood. The towers of Brahma and Hanoï revisited. Journal of Recreational Mathematics (JRM), 14(1):17-24, 1981. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail