Bounded Hanoi

Abstract

The classic Tower of Hanoi puzzle involves moving a set of disks on three pegs. The number of moves required for a given number of disks is easy to determine, but when the number of pegs is increased to four or more, this becomes more challenging. After 75 years, the answer for four pegs was resolved only recently, and this time complexity question remains open for five or more pegs. In this article, the space complexity, i.e., how many disks need to be accommodated on the pegs involved in the transfer, is considered for the first time. Suppose m disks are to be transferred from some peg L to another peg R using k intermediate work pegs of heights $j_1,\dots ,j_k$, then how large can m be? We denote this value by $H(j_1,\dots ,j_k)$. If k = 1, as in the classic problem, the answer is easy: $H(j)=j+1$. We have the exact value for two work pegs, but so far only very partial results for three or more pegs. For example, $H(10!,10!)=26336386137601$ and $H(0!,1!,2!,\dots ,10!)=16304749471397$, but we still do not know the value for $H(1,3,3)$.

MSC:

• Primary 00A08
• Secondary 68W40

Acknowledgment

We thank the reviewers for their valuable suggestions. The research of Kazuo Iwama is supported by KAKENHI, Ministry of Education, Japan. The research of Mike Paterson is supported by the Centre for Discrete Mathematics and its Applications (DIMAP).

Additional information

Notes on contributors

Kazuo Iwama

KAZUO IWAMA received his B.E., M.E., and Ph.D. degrees from Kyoto University. After retirement from the School of Informatics at Kyoto, he was with the Research Institute for Mathematical Sciences and the Academic Center for Computing and Media Studies, Kyoto University, and is currently with NTHU in Taiwan. Most of this work was done when he was with the Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic, from February to June 2020.

Mike Paterson

MIKE PATERSON (Ph.D., FRS) took degrees in mathematics at Cambridge and rose to fame as the co-inventor of Sprouts with John Conway. He evolved from president of the Trinity Mathematical Society to president of the European Association for Theoretical Computer Science, and migrated from MIT to the University of Warwick, where he has been in the Computer Science department for 50 years.