Bounded Hanoi
Kazuo Iwama, Mike Paterson · American Mathematical Monthly · 2022
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 j1,…,jk, then how large can m be? We denote this value by H(j1,…,jk). 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!,…,10!)=16304749471397, but we still do not know the value for H(1,3,3).