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

DOI10.4230/LIPICS.FUN.2016.5zbMATH Open1369.68231arXiv1602.03934OpenAlexW2963074027MaRDI QIDQ5282801FDOQ5282801

Jérémy Barbay

Publication date: 17 July 2017

Abstract: The problem of the Hanoi Tower is a classic exercise in recursive programming: the solution has a simple recursive definition, and its complexity and the matching lower bound are the solution of a simple recursive function (the solution is so easy that most students memorize it and regurgitate it at exams without truly understanding it). We describe how some very minor changes in the rules of the Hanoi Tower yield various increases of complexity in the solution, so that they require a deeper analysis than the classical Hanoi Tower problem while still yielding exponential solutions. In particular, we analyze the problem fo the Bouncing Tower, where just changing the insertion and extraction position from the top to the middle of the tower results in a surprising increase of complexity in the solution: such a tower of $n$ disks can be optimally moved in $sqrt{3}^n$ moves for $n$ even (i.e. less than a Hanoi Tower of same height), via $5$ recursive functions (or, equivalently, one recursion function with $5$ states).

Full work available at URL: https://arxiv.org/abs/1602.03934

zbMATH Keywords

recursivityBrähma towerdisk pileHanoï towerlevitating towerSelenite tower

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• HEX: scaling honeycombs is easier than scaling clock trees 👍 👎
• Short Notes: A Fast Algorithm for the Towers of Hanoi Problem 👍 👎
• An optimal algorithm to implement the Hanoi towers with parallel moves 👍 👎
• A loopless approach for constructing a fastest algorithm for the towers of hanoi problem 👍 👎
• Exponential vs. Subexponential Tower of Hanoi Variants 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎

This page was built for publication: Selenite Towers Move Faster Than Hanoï Towers, But Still Require Exponential Time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5282801)