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

1 Introduction

It is often extremely hard to formally prove the optimality of an algorithm, even if it looks beyond doubt. A good example is the 4-peg Tower of Hanoi problem. The Tower of Hanoi (TOH) is a popular puzzle whose origin dates back to 1883, due to French mathematician Édouard Lucas [6]. In its original version, there are three pegs on a board and m disks of different sizes are stacked on one peg in descending order of size. The puzzle requires us to move all the disks to another peg, while moving just one disk at a time, and never placing a larger disk on top of a smaller one. A simple recursive algorithm which runs in $2^m-1$ steps is well known. Proving its optimality is not difficult, due to the obvious fact that when the largest disk moves from one peg to another, all the other m – 1 disks must be on the third peg.

A natural extension of TOH is to increase the number of pegs from three to four or more, whereupon the situation changes drastically. Its time complexity, certainly smaller than the above $2^m-1$ steps, was first asked in the literature by Stewart [8] in 1939, and two years later, Stewart and Frame independently proposed what they call “optimal” algorithms without proof. The two algorithms turned out to be equivalent [9] and since then they have been known as the Frame–Stewart algorithm, and its optimality presented as a challenging open question. Indeed, as reported in [7], Donald Knuth wrote in a letter to Martin Gardner in 1979 that he doubted “if anyone will ever resolve the conjecture; it is truly difficult.”

After some partial solutions (e.g., [4]) and exhaustive checks up to some number of disks by computer [3], the optimality was proved by Bousch [1] in 2014 for four pegs. The solution for more pegs still remains open [2]. Thus the time complexity of TOH has been a popular topic, but there has been no literature about its space complexity. Judging by the history of the time complexity, the space complexity could be equally nontrivial. In this article, we provide some preliminary results and give an exact solution for the case of four pegs. By convention, disks are initially located on the leftmost peg (denoted by L) and they have to move to the rightmost one (denoted by R). The other pegs between L and R we call the work pegs, and use k for the number of them. The height of a peg is the maximum number of disks that can be held on the peg. Pegs L and R have unbounded height. We regard the finite heights of the work pegs as the space complexity of the problem. For k = 1, i.e., for the standard 3-peg model, it is easily seen that a work peg of height m – 1 suffices to execute the optimal algorithm and it is also necessary for any algorithm. For k = 2, Frame–Stewart needs a height of approximately $m-\sqrt{2m}$ for one work peg and $\sqrt{2m}$ for the other, but this is not necessary in general.

This article shows we can indeed use substantially shorter pegs for k = 2, the heights of which can be described exactly by a simple formula. Let H(i, j) denote the maximum number of disks that can be moved from L to R using two work pegs of height $i\ge 0$ and $j\ge 0$. Our main contribution is to prove$$H(i,j)=2ij+i+j+1.$$

So for m disks, it is sufficient to take i and j equal to a rounded value of $\sqrt{m/2}$, much smaller than the height needed for the Frame–Stewart algorithm. The lower bound proof is relatively easy, just by giving a recursive algorithm. Its optimality (the upper bound part), however, needs a lot more work. As in the standard model with one work peg, a key step in the analysis is when the largest disk leaves L and goes to one of the work pegs or to R. The other work peg can hold several disks, so there are many possible subsequent moves.

For general k, we give a recursive formula for a seemingly close lower bound for $H(j_1,j_2,\dots ,j_k)$. However, it is not likely that it can be presented as a closed-form formula, or that we can easily extend the upper bound proof for k = 2 to this general case. Surprisingly, if the successive work peg heights grow relatively slowly, satisfying $j_1=1$ and $j_{i+1}\le {(j_1+\cdots +j_i-1)}^2+1$ for $1\le i<k$, then the tight bound can be given as a simple formula, namely we can prove $H(j_1,j_2,\dots ,j_k)={(j_1+\cdots +j_k)}^2+1$.

2 Preliminaries

All the problems we will consider involve transferring the set of disks $1,2,\dots ,m$ from an unbounded initial peg L, via a set of bounded work pegs W, to an unbounded final peg R. In this article, W consists of some number k of pegs of heights $j_1,\dots ,j_k$ and we denote this storage structure as $W(j_1,\dots ,j_k)$.

We define $H(j_1,\dots ,j_k)$ to be the maximum number of disks that can be moved from L to R using $W(j_1,\dots ,j_k)$, e.g., $H(1)=2$.

A stack is any legal pile of disks, usually listed top-down, i.e., in order of increasing size. A disk move removes a disk from the top of the stack on one peg and places it on the top of the stack on another peg provided that it is smaller than the current top disk on that peg and the move does not produce a stack exceeding the height of that peg. The r-cone C_r is the stack of disks $(1,\dots ,r)$ and, for $1\le r\le s$, the (r, s)-frustum $F_s^r$ is the stack (or set) $(r,r+1,\dots ,s)$. We will find it convenient to extend these definitions such that C_r is the empty set when $r\le 0$, and $F_s^r=\left\{t\right|t>0\text{and}r\le t\le s\}$ is empty when r > s.

A configuration gives the contents of each peg. We denote a configuration C with the contents of L, R, and W being X, Y, and U, respectively, as $〈X\left|U\right|Y〉$. When the contents of $W(j_1,j_2)$, say, are given in more detail as U₁, U₂, we write $〈X|U_1\mathrm{}:\mathrm{}{U}_2|Y〉$. An empty set is denoted by “–”.

If a sequence σ of disk moves changes configuration C₁ to C₂, we write $C_1\stackrel{\sigma }{\Rightarrow }{C}_2$ or just $C_1\Rightarrow C_2$ when σ is unspecified. Since any sequence of disk moves is reversible, if $C_1\Rightarrow C_2$ then $C_2\Rightarrow C_1$. So we may write $C_1\iff C_2$ when $C_1\Rightarrow C_2$ and we want to emphasise that this is an equivalence relation.

We make precise an obvious “monotonicity” property: if some sequence of disk moves is feasible, then so is the subsequence obtained by eliminating some of the disks.

Lemma 1

(Monotonicity Lemma). Let S be the subset of disks that remains after some eliminations. Let C₁ and C₂ be two configurations and $C{\prime }_1=C_1\cap S$ and $C{\prime }_2=C_2\cap S$ be the configurations corresponding to C₁ and C₂ but restricted to the disks in S. If $C_1\Rightarrow C_2$ then $C{\prime }_1\Rightarrow C{\prime }_2$.

Proof.

For any sequence of moves σ, let $\sigma \prime$ be the sequence formed as follows: for any move $\gamma \in \sigma$ of disk d, if $d\in S$ then let $\gamma \prime =\gamma$, and if $d\notin S$ then $\gamma \prime$ is the null move. Clearly, if $C_1\stackrel{\sigma }{\Rightarrow }{C}_2$ then $C{\prime }_1\stackrel{\sigma \prime }{\Rightarrow }C{\prime }_2$. □

3 Single work peg

When there is just one work peg of bounded height, determining H(j) is fairly easy. The proof methods we introduce here will be used in later sections.

Theorem 2.

For all $j\ge 0,H(j)=j+1$.

Proof.

We first prove that $H(j)\ge j+1$. We show by induction on j and m that, for $m\le j+1$, C_m can be transferred from L to R using a single work peg of height j. This holds trivially for m = 0, and also for j = 0 since one disk can be transferred directly from L to R. Suppose now that j > 0, $H(j-1)\ge j$, and $C_{m-1}$ can be transferred from L to R. We want to show that if $m\le j+1$ then $〈C_m|-|-〉\Rightarrow 〈-|-|C_m〉$. The sequence we use below is not optimal in the number of moves, but is a better introduction to the more complicated transfers required later.

1. $〈C_m|-|-〉\Rightarrow 〈m|-|C_{m-1}〉$

   Using the inductive hypothesis, move $C_{m-1}$ from L to R leaving disk m on L.

2. $〈m|-|C_{m-1}〉\Rightarrow 〈-\left|m\right|C_{m-1}〉$

   Move disk m to W.

3. $〈-\left|m\right|C_{m-1}〉\Rightarrow 〈C_{m-1}\left|m\right|-〉$

   With space j – 1 remaining on W, by induction $C_{m-1}$ can be moved back to L.

4. $〈C_{m-1}\left|m\right|-〉\Rightarrow 〈-|-|C_m〉$

   Moving disk m to R, then $C_{m-1}$ from L to R, finishes the transfer.

For the upper bound, we want to prove that if $〈C_m|-|-〉\Rightarrow 〈-|-|C_m〉$ when W is a single peg of height j then $m\le j+1$. Again we proceed by induction on j. The result holds for j = 0, since C₂ cannot be transferred from L to R without W. We assume as inductive hypothesis that $H(j-1)\le j$, and consider a supposed transfer $〈C_m|-|-〉\Rightarrow 〈-|-|C_m〉$, where W is a peg of height j.

If disk m moves directly from L to R, then the other m – 1 disks must all be on W, so $m\le j+1$ as required. Supposing that m never moves directly between L and R, consider the configuration A immediately after disk m moves from L to W for the last time, so $A=〈-\left|m\right|C_{m-1}〉$. Let B be the configuration immediately before the next time that m moves from W to R. So $B=〈C_{m-1}\left|m\right|-〉$ and m remains in W all the time between A and B. During this period $C_{m-1}$ is transferred from R to L using only the remaining j – 1 positions on the work peg. This implies that $m-1\le H(j-1)$, and $H(j-1)\le j$ by induction. Hence $m\le j+1$, completing the proof. ■

4 Unit work pegs

Define $HU(k)=H(1,\dots ,1)$ where there are k work pegs each of height one. As seen above, $HU(1)=2$. To help the reader become familiar with the notation, we show the transfer of five disks in 25 moves using two unit work pegs. Here we merely use a superscript on the “$\Rightarrow$” to give the number of disk moves involved, leaving the reader to determine the sequence in detail. A concatenation of stacks on one peg is separated by commas, e.g., $C_2,4$ represents the cone {1, 2} on top of the disk 4. It should be noted that a cone on top of a suitably sized frustum will result in a larger cone, so $C_r,F_s^{r+1}=C_s$.$$\begin{array}{c}〈C_5|-\mathrm{}:\mathrm{}-|-〉\stackrel{5}{\Rightarrow }〈F_5^4|-\mathrm{}:\mathrm{}-|C_3〉\stackrel{3}{\Rightarrow }〈4|-\mathrm{}:\mathrm{}5|C_3〉\stackrel{3}{\Rightarrow }〈C_2,4|-\mathrm{}:\mathrm{}5|3〉\\ \stackrel{3}{\Rightarrow }〈C_2,4|-\mathrm{}:\mathrm{}-|3,5〉\stackrel{2}{\Rightarrow }〈4|1\mathrm{}:\mathrm{}-|F_3^2,5〉\stackrel{2}{\Rightarrow }〈2|1\mathrm{}:\mathrm{}4|3,5〉\\ \stackrel{2}{\Rightarrow }〈C_2|3\mathrm{}:\mathrm{}4|5〉\stackrel{2}{\Rightarrow }〈C_2|-\mathrm{}:\mathrm{}-|F_5^3〉\stackrel{3}{\Rightarrow }〈-|-\mathrm{}:\mathrm{}-|C_5〉\end{array}$$

Lemma 4 shows that five is the maximum number of disks that can be transferred using two unit work pegs, but we do not know whether the number of moves used above can be reduced.

Since W contains only unit pegs, there is no point in disk moves between pegs in W and a configuration needs only define the set of at most k disks in W without specifying their positions. In this case of unit pegs, a frustum $F_s^r$ in W just refers to the set of disks $\{r,r+1,\dots ,s\}$ on $r-s+1$ pegs without regard to their order.

The lower bound is provided by Lemma 3.

Lemma 3.

$HU(k)\ge k^2+1$ for $k\ge 0$.

Proof.

To prove the result, we show by induction on m and k that, for all $m\le k^2+1$, C_m can be transferred from L to R using the set W of k unit work pegs. The result is true for $m\le 1$, for any $k\ge 0$, since C₁ can be transferred without using W.

We assume the inductive hypothesis for $0\le k\prime <k$ and for all $m\prime <m$, and consider the transfer of C_m from L to R using k unit work pegs where $1<m\le k^2+1$.

1. $〈C_m|-|-〉\Rightarrow 〈F_m^{m-k+1}|-|C_{m-k}〉$

Move $C_{m-k}$ from L to R. This is feasible, by induction on m since k > 0.

1. $〈F_m^{m-k+1}|-|C_{m-k}〉\Rightarrow 〈-\left|F_m^{m-k+1}\right|C_{m-k}〉$

Move the (at most) k disks in the frustum $F_m^{m-k+1}$ to the work pegs W.

1. $〈-\left|F_m^{m-k+1}\right|C_{m-k}〉\Rightarrow 〈F_{m-1}^{m-k+1}\left|m\right|C_{m-k}〉$

Move $F_{m-1}^{m-k+1}$ back to L, leaving disk m occupying one of the work pegs.

1. $〈F_{m-1}^{m-k+1}\left|m\right|C_{m-k}〉\Rightarrow 〈C_{m-2k+1},F_{m-1}^{m-k+1}\left|m\right|F_{m-k}^{m-2k+2}〉$

Move $C_{m-2k+1}$ from the top of R back to L using the k – 1 empty work pegs, by induction on k, since $m-2k+1\le k^2+1-2k+1={(k-1)}^2+1$.

1. $〈C_{m-2k+1},F_{m-1}^{m-k+1}\left|m\right|F_{m-k}^{m-2k+2}〉\Rightarrow 〈C_{m-2k+1},F_{m-1}^{m-k+1}|F_{m-k}^{m-2k+2},m|-〉$

Move the remaining k – 1 disks from R to the k – 1 empty work pegs.

1. $〈C_{m-2k+1},F_{m-1}^{m-k+1}|F_{m-k}^{m-2k+2},m|-〉\mathrm{\hspace{1em}}\mathrm{\hspace{1em}}\Rightarrow 〈C_{m-2k+1},F_{m-1}^{m-k+1}|-|F_{m-k}^{m-2k+2},m〉$

Move disk m to R and place $F_{m-k}^{m-2k+2}$ on top of this on R.

1. $〈C_{m-2k+1},F_{m-1}^{m-k+1}|-|F_{m-k}^{m-2k+2},m〉\mathrm{\hspace{1em}}\mathrm{\hspace{1em}}\Rightarrow 〈F_{m-1}^{m-k+1}|-|C_{m-2k+1},F_{m-k}^{m-2k+2},m〉=〈F_{m-1}^{m-k+1}|-|C_{m-k},m〉$

Move $C_{m-2k+1}$ from the top of L to R, resulting in the cone $C_{m-k}$. This is feasible using the k work pegs by induction on m.

1. $〈F_{m-1}^{m-k+1}|-|C_{m-k},m〉\Rightarrow 〈C_{m-1}|-|m〉$

Move $C_{m-k}$ from the top of R back to L. This is feasible using the k work pegs by induction on m.

1. $〈C_{m-1}|-|m〉\Rightarrow 〈-|-|C_m〉$

Move $C_{m-1}$ from L to R to complete the task. ■

For the upper bound:

Lemma 4.

$HU(k)\le k^2+1$ for $k\ge 0$.

Proof.

The result is true for k = 0 since $HU(0)=1$. To prove the result by induction on k, we assume that $HU(k-1)\le {(k-1)}^2+1$, where $k\ge 1$, and prove that $HU(k)\le k^2+1$.

Suppose the number of disks is m. We want to prove that if $〈C_m|-|-〉\Rightarrow 〈-|-|C_m〉$ then $m\le k^2+1$. If m can move directly from L to R, then $m\le k+1\le k^2+1$, as required.

Otherwise, as in the proof of Theorem 2, we focus on two critical stages in the sequence of moves. Let A be the configuration just after the last time that disk m moves from L to W, and B the configuration after which m moves from W to R the next time after A. Suppose $A=〈-|U_1,m|Y〉$ and $B=〈X|U_2,m|-〉$. Let $Z=X\cap Y$, so $\left|Z\right|=|X\cap Y|=\left|X\right|+\left|Y\right|-|X\cup Y|\ge 2(m-k)-(m-1)=m-2k+1$, since $\left|X\right|\ge m-k$, $\left|Y\right|\ge m-k$, and $|X\cup Y|\le m-1$. The monotonicity lemma (Lemma 1) shows that the set of disks Z can be transferred from R to L using only k – 1 pegs in W. By the inductive hypothesis, $m-2k+1\le HU(k-1)\le {(k-1)}^2+1$, and so $m\le k^2+1$, completing the proof. ■

Together, Lemmas 3 and 4 establish the precise value for $HU$.

Theorem 5.

$HU(k)=k^2+1$ for $k\ge 0$.

We conclude this section with a simple consequence of this theorem.

Theorem 6.

$H(j_1,\dots ,j_k)\le {({\sum }_{i=1}^k{j}_i)}^2+1$.

Proof.

It is easy to show that any work peg P of height a + b can be simulated by the pair of work pegs $P\prime$ and $P″$ of heights a and b, respectively. If there are b or fewer disks on P, then they are stored on $P″$, otherwise the largest b disks are on $P″$ and the rest on $P\prime$.

Thence, $W(j_1,\dots ,j_k)$ can be simulated by ${\sum }_{i=1}^k{j}_i$ unit pegs, and the result follows from Theorem 5. ■

5 Two work pegs

We show matching upper and lower bounds for H(i, j), the maximum number of disks that can be transferred from L to R using two work pegs P₁ and P₂ of heights i and j, respectively. A major difference from the case of unit pegs is that it might be advantageous to move the largest disk within W. This turns out not to be the case with just two pegs, but the possibility complicates the proof of the upper bound. We begin with the lower bound.

Lemma 7.

For all $i,j\ge 0,H(i,j)\ge 2ij+i+j+1$.

Proof.

The proof is by induction on i and j. The result holds when either i = 0 or j = 0 since this corresponds to a single work peg and it is known that $H(i)=i+1$. To show the bound for H(i, j), we assume as inductive hypothesis that the result holds for all $(i\prime ,j\prime )$ with $i\prime +j\prime <i+j$. We may also assume that $i\ge 1,j\ge 1$ and consider the transfer of the cone C_m from L to R, where $m\le 2ij+i+j+1$. For this we again use induction, this time on m. If $m\le 2ij-i+j$, then C_m can be transferred, since $m\le H(i,j-1)$ by induction on i + j. So we now assume that $2ij-i+j<m\le 2ij+i+j+1$ and that $H(i,j)\ge m-1$.

We show how C_m is transferred from L to R. Here we assume without loss of generality that $i\le j$. If j < i, then the same algorithm is used with the roles of P₁ and P₂ reversed.

1. $〈C_m|-\mathrm{}:\mathrm{}-|-〉\Rightarrow 〈F_m^{m-i}|-\mathrm{}:\mathrm{}-|C_{m-i-1}〉$

Transfer $C_{m-i-1}$ from L to R. This is feasible by the inductive hypothesis on m.

1. $〈F_m^{m-i}|-\mathrm{}:\mathrm{}-|C_{m-i-1}〉\Rightarrow 〈-|F_{m-1}^{m-i}\mathrm{}:\mathrm{}m|C_{m-i-1}〉$

Move the frustum $F_{m-1}^{m-i}$ to the work peg P₁, using work peg P₂, since $i\le j+1$, and then move disk m to P₂.

1. $〈-|F_{m-1}^{m-i}\mathrm{}:\mathrm{}m|C_{m-i-1}〉\Rightarrow 〈F_{m-1}^{m-i}|-\mathrm{}:\mathrm{}m|C_{m-i-1}〉$

Move $F_{m-1}^{m-i}$ back to L, using the remaining capacity j – 1 of P₂ since $i\le j$.

1. $〈F_{m-1}^{m-i}|-\mathrm{}:\mathrm{}m|C_{m-i-1}〉\Rightarrow 〈C_{m-2i-1},F_{m-1}^{m-i}|-\mathrm{}:\mathrm{}m|F_{m-i-1}^{m-2i}〉$

Move $C_{m-2i-1}$ from the top of $C_{m-i-1}$ on R back to L. This is feasible using the remaining capacity $(i,j-1)$ of work pegs, since $m-2i-1\le 2ij+i+j+1-2i-1=2i(j-1)+i+j\le H(i,j-1)$, by the inductive hypothesis.

1. $〈C_{m-2i-1},F_{m-1}^{m-i}|-\mathrm{}:\mathrm{}m|F_{m-i-1}^{m-2i}〉\Rightarrow 〈C_{m-2i-1},F_{m-1}^{m-i}|-\mathrm{}:\mathrm{}-|F_{m-i-1}^{m-2i},m〉$

Disk m is inserted underneath a frustum of size i, just like a reversal of steps 2 and 3 above.

1. $〈C_{m-2i-1},F_{m-1}^{m-i}|-\mathrm{}:\mathrm{}-|F_{m-i-1}^{m-2i},m〉\Rightarrow 〈C_{m-1}|-\mathrm{}:\mathrm{}-|m〉$

Move $C_{m-2i-1}$ from the top of L to R and then move the resulting $C_{m-i-1}$ from the top of R back to L. These operations are feasible using the now-empty work pegs, by induction on m.

1. $〈C_{m-1}|-\mathrm{}:\mathrm{}-|m〉\Rightarrow 〈-|-\mathrm{}:\mathrm{}-|C_m〉$

Move $C_{m-1}$ from L to R to complete the task. ■

In the algorithm that provided the lower bound, the largest disk moved from L to W, then remained on the same peg in W and finally moved from W to R. We now have to deal with the possibility that the largest disk may move between pegs in W. In preparation, we prove two lemmas which establish useful properties of sequences that satisfy a requirement, such as moving some set of disks from one peg to another during some interval.

The first lemma shows, under some conditions, that if a disk d can move from W to R, then there is a sequence whose net effect is only to remove d from W and to insert it into the present stack on R. In the rest of this section, we often consider sequences of moves such that the largest disk m remains in W throughout. We write “$\stackrel{\Rightarrow }{\mathit{-}}$” for the operation of such a sequence.

For a configuration $C=〈-|U_1\mathrm{}:\mathrm{}{U}_2|V〉$ where m is in W, we say disk $d\in U_1\cup U_2$ can reach R if $C\stackrel{\Rightarrow }{\mathit{-}}〈T|U_1^{\prime }\mathrm{}:\mathrm{}{U}_2^{\prime }|V\prime 〉$ where $d\in V\prime$. Furthermore, disk d in U₁ can shift to R if $C\stackrel{\Rightarrow }{\mathit{-}}〈-|U_1\setminus \{d\}\mathrm{}:\mathrm{}{U}_2|V\cup \left\{d\right\}〉$, i.e., the only difference made by the sequence is to remove disk d from its work peg and insert it into place on R. The definition for $d\in U_2$ is similar.

Lemma 8.

While m remains in W throughout, for any configuration with L empty, if d is the largest (other than m) of the set of disks in W that can reach R, then d can shift to R.

Before the proof, let us see an example to illustrate the lemma. Let $W=(3,3)$ and $C=〈-|3,4,\mathbf{5}\mathrm{}:\mathrm{}--7|1,2,6〉$. To help the reader, we use hyphens to represent the spare capacity on work pegs. Here, m = 7, and d = 5 is the disk of interest. Using the spare capacity in P₂, stacks of height three can be moved from one peg to another. So$$〈-|3,4,\mathbf{5}\mathrm{}:\mathrm{}--7|1,2,6〉\stackrel{\Rightarrow }{\mathit{-}}〈1,2,6|3,4,\mathbf{5}\mathrm{}:\mathrm{}--7|-〉\stackrel{\Rightarrow }{\mathit{-}}〈1,2,6|---\mathrm{}:\mathrm{}--7|3,4,\mathbf{5}〉.$$

We see that d can indeed reach R. The lemma constructs a sequence of moves from C which can shift d to R. For example,$$\begin{array}{c}〈-|3,4,\mathbf{5}\mathrm{}:\mathrm{}--7|1,2,6〉\stackrel{\Rightarrow }{\mathit{-}}〈1,2|3,4,\mathbf{5}\mathrm{}:\mathrm{}--7|6〉\stackrel{\Rightarrow }{\mathit{-}}〈1,2|---\mathrm{}:\mathrm{}3,4,7|\mathbf{5},6〉\\ \stackrel{\Rightarrow }{\mathit{-}}〈1,2|-3,4\mathrm{}:\mathrm{}--7|\mathbf{5},6〉\stackrel{\Rightarrow }{\mathit{-}}〈-|-3,4\mathrm{}:\mathrm{}--7|1,2,\mathbf{5},6〉.\end{array}$$

Proof.

Let $C=〈-|U_1\mathrm{}:\mathrm{}{U}_2|V〉$ where $m\in W$, and suppose that $d\in U_1$ is the largest disk (other than m) in W that can reach R. (There may be larger disks in W that cannot reach R.) Suppose that σ is a sequence of moves starting from C up to but not including the first move in which d reaches R. We assume that m remains in W throughout σ.

Let Z be the subset of disks in V that are larger than d. It may be that during σ some disks in Z move out of R. We show that such moves can be eliminated. Consider the sequence σ₁ that is σ but omitting all moves of disks in Z. By the monotonicity lemma, σ₁ is well-defined: all moves in σ₁ are possible because they are between configurations in which L and W hold subsets of their contents at the corresponding step of σ. Disks in Z remain on R and cannot obstruct any other disks or the move of d to R. Let σ₂ be the sequence consisting of σ₁ followed by the move of d to R, followed by the reversal of σ₁ also omitting any moves of d. By monotonicity again (disk d has been omitted), this reversal is valid, and σ₂ has the required property of returning all disks to their position in C except for d, which has been inserted in R. The case with d initially in U₂ is similar. ■

A simple, but useful, lemma finally prepares us for our upper bound result.

Lemma 9.

If $〈C_m|-|-〉\iff 〈-|-|C_m〉$, then $〈U_1|-|V_1〉\iff 〈U_2|-|V_2〉$ for any U₁,V₁,U₂,V₂ with disjoint unions $U_1\dot{\cup }{V}_1=U_2\dot{\cup }{V}_2=C_m$.

Proof.

By monotonicity, for any $r\le m$, cone C_r can be moved between L and R. The stacks U₁ and V₁ can be merged into C_m by forming $C_1,\dots ,C_m$ successively. This increasing set of cones is made by shuttling partial cones between L and R, collecting the disks from U₁ and V₁ in increasing order. The same holds for U₂ and V₂. ■

Now we can prove our upper bound for two work pegs.

Lemma 10.

For all $i,j\ge 0,H(i,j)\le 2ij+i+j+1$.

Proof.

As in Lemma 7, the proof is by induction on i and j, and then on m. The result holds when either i = 0 or j = 0, since this corresponds to a single work peg and $H(i)=i+1$. To show the bound for H(i, j), we assume as inductive hypothesis that the result holds for all $(i\prime ,j\prime )$ with $i\prime +j\prime <i+j$. We may also assume that $i\ge 1$ and $j\ge 1$.

For our inductive proof, let $m=H(i,j)$. By the definition of H(i, j),$$〈C_m|-|-〉\stackrel{\sigma }{\Rightarrow }〈-|-|C_m〉,$$for some sequence of moves σ. We focus on one particular segment $\sigma \prime$ of σ during which the largest disk m remains in W. Let $\sigma \prime$ begin at configuration $A=〈-|m\mathrm{}:\mathrm{}{X}_1|Y_1〉$, when m has just moved for the last time from L to W, onto P₁ say, and finish at $B=〈Y_2|m\mathrm{}:\mathrm{}{X}_2|-〉$ or $〈Y_2|X_2\mathrm{}:\mathrm{}m|-〉$, the next time that m is about to move from W to R.

Disk m is on L just before the start of $\sigma \prime$ and on R just after the end of $\sigma \prime$, and by Lemma 7, $m=H(i,j)\ge 2ij+i+j+1>i+j+1$ since i > 0 and j > 0. Hence disk m cannot move directly from L to R, since the other m – 1 disks exceed the total capacity of W which is i + j. Therefore $\sigma \prime$ is well-defined.

Recall that $\stackrel{\Rightarrow }{\mathit{-}}$ is used for a sequence where the largest disk m remains in W throughout.

We first consider the case where disk m remains on P₁ throughout $\sigma \prime$, so$$A=〈-|m\mathrm{}:\mathrm{}{X}_1|Y_1〉\stackrel{{\sigma }^{\prime }}{\begin{array}{c}\Rightarrow \\ \mathit{-}\end{array}}B=〈Y_2|m\mathrm{}:\mathrm{}{X}_2|-〉.$$

Since each of X₁ and X₂ are on P₂ at some time, $|X_1\cup X_2|\le \left|X_1\right|+\left|X_2\right|\le 2j$. Let $Z=\{1,\dots ,m-1\}\setminus (X_1\cup X_2)$. Then, by the monotonicity lemma, we may ignore disks in $X_1\cup X_2$ to show that$$〈-|m\mathrm{}:\mathrm{}-|Z〉\stackrel{{\sigma }^{\prime }\prime }{\begin{array}{c}\Rightarrow \\ \mathit{-}\end{array}}〈Z|m\mathrm{}:\mathrm{}-|-〉,$$

for some sequence $\sigma ″$, and where $\left|Z\right|\ge m-1-2j$. Since disk m remains on P₁ throughout $\sigma ″$, we have $m-1-2j\le H(i-1,j)$. Hence by induction,$$\begin{array}{c}H(i,j)=m\le H(i-1,j)+1+2j\le (2(i-1)j+(i-1)+j+1)+1+2j\\ =2ij+i+j+1,\end{array}$$as required for this case. The case where m moves to P₂ at time A, and remains there throughout $\sigma \prime$, is similar.

Now we consider the case where disk m does move between work pegs during $\sigma \prime$. The above argument fails because a set Z of size $H(i,j-1)$ might be transferred if disk m can be moved to P₂, and $H(i,j-1)>H(i-1,j)$ if i < j. We used the fact that $\left|X_1\right|\le j$, while for the general case we want to have $\left|X_1\right|\le \min (i,j)$.

For disk m to move from P₁ to P₂, each disk on P₂ in configuration A has to be removed from W, either to L directly or else via R. For the latter, any such disk can reach R and so we need Lemma 8.

Suppose that $D=(d_1,\dots ,d_r)$ is the set of disks in decreasing order of size that are on P₂ and can reach R. By Lemma 8, d₁ can be shifted to R, resulting in configuration $C\prime$. Now d₂ can still reach R starting from $C\prime$ (by first reversing the sequence shifting d₁ if necessary), and is now the largest disk on P₂ that can reach R. By Lemma 8, d₂ can be shifted to R, and so on, until all of D has been shifted. The result is a configuration $A\prime =〈-|m\mathrm{}:\mathrm{}X{\prime }_1|Y{\prime }_1〉$ where no disk in $X{\prime }_1$ can reach R.

Suppose $A″=〈U_1|m\mathrm{}:\mathrm{}-|V_1〉$ is the configuration before the first move of m from P₁ to P₂ during $\sigma \prime$. Then$$A\prime =〈-|m\mathrm{}:\mathrm{}X{\prime }_1|Y{\prime }_1〉\stackrel{\iff }{\mathit{-}}A\stackrel{\Rightarrow }{\mathit{-}}A″=〈U_1|m\mathrm{}:\mathrm{}-|V_1〉,$$where $X{\prime }_1\subseteq U_1$, since no disk in $X{\prime }_1$ can reach R.

By monotonicity, if we consider only disks in $X{\prime }_1\cup \left\{m\right\}$ and only moves between L and W and within W, we may ignore peg R completely and derive$$〈-|m\mathrm{}:\mathrm{}X{\prime }_1|\stackrel{\Rightarrow }{\mathit{-}}〈X{\prime }_1|m\mathrm{}:\mathrm{}-|.$$

Therefore, $\left|X{\prime }_1\right|\le H(i-1)=i$ and so $\left|X{\prime }_1\right|\le \min (i,j)$.

By a symmetric argument, if $B=〈Y_2|m\mathrm{}:\mathrm{}{X}_2|-〉$ then $B\prime =〈Y{\prime }_2|m\mathrm{}:\mathrm{}X{\prime }_2|-〉\stackrel{\Rightarrow }{\mathit{-}}B$ for some $X{\prime }_2,Y{\prime }_2$ where $\left|X{\prime }_2\right|\le \min (i,j)$, and similarly if m is on P₂ in B.

As in the cases where m never switches work pegs, we define $Z=\{1,\dots ,m-1\}\setminus (X{\prime }_1\cup X{\prime }_2)$, but now we have the stronger inequality $\left|Z\right|\ge m-1-2\min (i,j)$. Again by the monotonicity lemma, we may ignore disks in $X_1^{\prime }\cup X_2^{\prime }$, and so$$〈-|m\mathrm{}:\mathrm{}-|Z〉\stackrel{{\sigma }^{\prime }\prime }{\begin{array}{c}\Rightarrow \\ \mathit{-}\end{array}}〈Z|m\mathrm{}:\mathrm{}-|-〉,$$for some sequence $\sigma ″$, and where $\left|Z\right|\ge m-1-2\min (i,j)$.

What remains to be proved is that moving m between P₁ and P₂ cannot achieve the transfer of more than $\max (H(i-1,j),H(i,j-1))$ disks.

Let $r=1+\max (H(i-1,j),H(i,j-1))$. It is sufficient to show that there can be no sequence τ such that$$〈-|m\mathrm{}:\mathrm{}-|C_r〉\stackrel{\tau }{\begin{array}{c}\Rightarrow \\ \mathit{-}\end{array}}〈C_r|m\mathrm{}:\mathrm{}-|-〉.$$

It is not relevant here whether m is on P₁ or P₂ in these configurations. Any such sequence τ consists of segments where m remains on the same work peg, separated by moves of m between pegs. We focus on the positions of disk r at each such move of m. Clearly r is on L or R at these moves. Suppose r switches between L and R during one of these segments $\tau \prime$, so$$F=〈U|m\mathrm{}:\mathrm{}-|V〉\stackrel{\tau \prime }{\begin{array}{c}\Rightarrow \\ \mathit{-}\end{array}}〈V\prime |m\mathrm{}:\mathrm{}-|U\prime 〉=G,$$where $r\in U$ and $r\in U\prime$, or similarly with $r\in V$ and $r\in V\prime$.

Since $r-1=\max (H(i-1,j),H(i,j-1))$, we may use the method in Lemma 9 to collect $U\setminus \left\{r\right\}$ and V into $C_{r-1}$ on L, and $U\prime \setminus \left\{r\right\}$ and $V\prime$ into $C_{r-1}$ on R. Hence$$\begin{array}{c}F\stackrel{\iff }{\mathit{-}}〈C_{r-1},r|m\mathrm{}:\mathrm{}-|-〉=〈C_r|m\mathrm{}:\mathrm{}-|-〉\\ \stackrel{\iff }{\mathit{-}}〈-|m\mathrm{}:\mathrm{}-|C_r〉=〈-|m\mathrm{}:\mathrm{}-|C_{r-1},r〉\stackrel{\iff }{\mathit{-}}G.\mathrm{}\end{array}$$

This gives a contradiction since at most $H(i-1,j)$ disks can be transferred from L to R while m remains on P₁, and $r>H(i-1,j)$, and similarly where m is on P₂ and $r>H(i,j-1)$. So cone C_r cannot be transferred from L to R while m remains on P₁ nor while m remains on P₂ and, for any move of m between P₁ and P₂, r is either on L or on R.

Therefore $\left|Z\right|\le \max (H(i-1,j),H(i,j-1))$, and hence, by induction,$$\begin{array}{c}H(i,j)=m\le \left|Z\right|+2\min (i,j)+1\\ \le \max (H(i-1,j),H(i,j-1))+2\min (i,j)+1\\ \le \max (2(i-1)j,2i(j-1))+i+j+2\min (i,j)+1\\ =2ij+i+j+1+2\max (-i,-j)+2\min (i,j)\\ =2ij+i+j+1.\mathrm{}■\end{array}$$

Together, Lemmas 7 and 10 establish

Theorem 11.

For all $i,j\ge 0,H(i,j)=2ij+i+j+1$.

6 More work pegs

When there are three or more work pegs, we have some partial results. Theorem 12 gives a simple formula similar to that in Theorem 11. Theorem 14 gives an improved lower bound in the form of a recursive formula, but there does not seem to be an equivalent explicit formula. Theorem 15 gives an exact result when work peg heights are sufficiently slowly growing. Finally, when we restrict our attention to the case of three work pegs, we have an improved algorithm in Theorem 17 which could even be optimal.

We begin with the easy lower bound which is an explicit polynomial formula proved in much the same way as Lemma 7.

Theorem 12.

For all $k\ge 0$ and nonnegative $j_1,\dots ,j_k$, $$H(j_1,\dots ,j_k)\ge 2\sum _{u<v}{j}_u{j}_v+\sum _{w=1}^k{j}_w+1.$$

Proof.

For any $k\ge 0$, the proof by induction on $j_1,\dots ,j_k$ is analogous to that in Lemma 7. The base of the induction holds when j_w = 0 for $1\le w\le k$, and a single disk can be transferred directly from L to R. Suppose without loss of generality that j_k is the height of a largest work peg. Let$$m=2\sum _{u<v}{j}_u{j}_v+\sum _{w=1}^k{j}_w+1\hspace{1em}\text{and}\hspace{1em}s=\sum _{w=1}^{k-1}{j}_w.$$

For ease of notation we define the frusta, $F^{(i)}$, where $(F^{(1)},\dots ,F^{(k-1)})=F_{m-1}^{m-s}$ and $\left|F^{(i)}\right|=j_i$, so $F^{(1)}=F_{m-s+j_1-1}^{m-s}$, etc.

Following a similar sequence to that used in the proof of Lemma 7, we show that C_m can be transferred from L to R using $W(j_1,\dots ,j_k)$, establishing that $H(j_1,\dots ,j_k)\ge m$ as required.

1. $〈C_m|-\mathrm{}:\mathrm{}\cdots \mathrm{}:\mathrm{}-|-〉\Rightarrow 〈F_m^{m-s}|-\mathrm{}:\mathrm{}\cdots \mathrm{}:\mathrm{}-|C_{m-s-1}〉$

   The cone $C_{m-s-1}$ is transferred from L to R.

2. $〈F_m^{m-s}|-\mathrm{}:\mathrm{}\cdots \mathrm{}:\mathrm{}-|C_{m-s-1}〉\Rightarrow 〈-|F^{(1)}\mathrm{}:\mathrm{}\cdots \mathrm{}:\mathrm{}{F}^{(k-1)}:\mathrm{}m|C_{m-s-1}〉$

   Using P_k, the s disks in $F_{m-1}^{m-s}$ are transferred to fill $P_1,\dots ,P_{k-1}$ with $F^{(1)},\dots ,F^{(k-1)}$, respectively, and disk m is moved from L to P_k.

3. $〈-|F^{(1)}\mathrm{}:\mathrm{}\cdots \mathrm{}:\mathrm{}{F}^{(k-1)}:\mathrm{}m|C_{m-s-1}〉\Rightarrow 〈F_{m-1}^{m-s}|-\mathrm{}:\mathrm{}\cdots \mathrm{}:\mathrm{}-:\mathrm{}m|C_{m-s-1}〉$

   The remaining capacity $j_k-1$ of P_k is sufficient to transfer the contents of all the other work pegs back to L.

4. $〈F_{m-1}^{m-s}|-\mathrm{}:\mathrm{}\cdots \mathrm{}:\mathrm{}-:\mathrm{}m|C_{m-s-1}〉\Rightarrow 〈C_{m-2s-1},F_{m-1}^{m-s}|-\mathrm{}:\mathrm{}\cdots \mathrm{}:\mathrm{}-:\mathrm{}m|F_{m-s-1}^{m-2s}〉$

   $C_{m-2s-1}$ is transferred back from the top of R to L, since, as verified below, $m-2s-1\le H(j_1,\dots ,j_{k-1},j_k-1)$.

5. $〈C_{m-2s-1},F_{m-1}^{m-s}|-\mathrm{}:\mathrm{}\cdots \mathrm{}:\mathrm{}-:\mathrm{}m|F_{m-s-1}^{m-2s}〉\Rightarrow 〈C_{m-2s-1},F_{m-1}^{m-s}|-\mathrm{}:\mathrm{}\cdots \mathrm{}:\mathrm{}-|F_{m-s-1}^{m-2s},m〉$

   Disk m is inserted beneath the frustum of size s on R, just like a reversal of the procedure in steps 2 and 3 which extracted m from beneath $F_{m-1}^{m-s}$ on L.

6. $〈C_{m-2s-1},F_{m-1}^{m-s}|-\mathrm{}:\mathrm{}\cdots \mathrm{}:\mathrm{}-|F_{m-s-1}^{m-2s},m〉\Rightarrow 〈-|-\mathrm{}:\mathrm{}\cdots \mathrm{}:\mathrm{}-|C_m〉$

   The final stages are as in the proof of Lemma 7. The cone $C_{m-2s-1}$ is transferred from L to R, producing $C_{m-s-1}$. This is then transferred back to L, producing $C_{m-1}$, which is finally moved to R, finishing the process.

Finally we check that $m-2s-1\le H(j_1,\dots ,j_{k-1},j_k-1)$:$$\begin{array}{c}m-2s-1=2\sum _{1\le u<v\le k}{j}_u{j}_v+\sum _{w=1}^k{j}_w+1-2s-1\\ =2\sum _{1\le u<v\le k-1}{j}_u{j}_v+2(j_k-1)s+\sum _{w=1}^{k-1}{j}_w+(j_k-1)+1\\ \le H(j_1,\dots ,j_{k-1},j_k-1),\end{array}$$by induction. ■

The corollary gives a polynomial formula when the work pegs are of equal height.

Corollary 13.

If $j_1=\cdots =j_k=j$, then $H(j_1,\dots ,j_k)\ge k(k-1)j^2+kj+1$.

For two work pegs, we showed in the proof of Lemma 10 that no move within W of the largest disk could be useful. This is not the case when there are more than two pegs. Theorem 12 gives $H(1,1,2)\ge 15$, but, as we will see in Theorem 14, this bound can be improved to 17. The reader may wish to explore this case now, starting with a transfer of C₁₃ from L to R.

Improved multipeg algorithm

We outline the transfer of m disks with work space $W(j_1,\dots ,j_k)$. In the course of our recursive algorithms, we will encounter the work spaces W(0) and $W()$, where there is either a single work peg with zero height or no work peg at all. In these cases, just a single disk can be transferred, i.e., $H(0)=H()=1$.

The work pegs should be sorted in order of height, so we assume $j_1\le \cdots \le j_k$. In the first stage of the algorithm, an appropriately sized cone C_s is transferred from L to R recursively.$$〈C_m|-:\cdots :-|-〉\Rightarrow 〈F_m^{s+1}|-:\cdots :-|C_s〉.$$

In the second stage, the longest work peg P_k is loaded with m_k disks by using all the other work pegs. We continue in this way loading $m_{k-1},\dots ,m_1$ disks on each of $P_{k-1},\dots ,P_1$ in turn, using all the currently empty work pegs. We will choose each $m_i\le H(j_1,\dots ,j_{i-1})$, and choose s so that $m-s={\sum }_{i=1}^k{m}_i$. We define frusta $F^{(1)},\dots ,F^{(k)}$ as in Theorem 12, but now with $\left|F^{(i)}\right|=m_i$, and $(F^{(k)},\dots ,F^{(1)})=F_m^{s+1}$. The effect of this second stage is therefore$$〈F_m^{s+1}|-\mathrm{}:\mathrm{}\cdots \mathrm{}:\mathrm{}-|C_s〉\Rightarrow 〈-|F^{(1)}\mathrm{}:\mathrm{}\cdots \mathrm{}:\mathrm{}{F}^{(k)}|C_s〉,$$and L is empty after these transfers. The transfer of disks from L to P₁ has no other work peg to help. Therefore $m_1=H()=1$ and m is the only disk on P₁.

In the third stage of the algorithm, disk m remains in W but all other disks in W are returned to L, clearing pegs $P_2,P_3,\dots ,P_k$ in succession. At most j₁ disks can be moved back from P₂ since there is only free space $j_1-1$ on P₁. We choose therefore, $m_2=\min (j_2,j_1)$. From now on there is more than one work peg to assist the transfer of disks from P_i to L, but one of these must contain disk m. It might seem best for disk m to be on a longest peg $P_{i-1}$ at this time, giving total work space $W(j_1,\dots ,j_{i-2},j_{i-1}-1)$ for this transfer. This is true when only two work pegs are used, but we know, for example, that $H(1,2,3)>H(2,2,2)$, so with work space $W(2,2,3)$ it would be better to put m on P₁. To account for this, it is convenient to define the function K.( ∗ ) $$\begin{array}{c}K(j_1,\dots ,j_k)=\max (H(j_1-1,j_2,\dots ,j_k),H(j_1,j_2-1,\dots ,j_k),\dots ,\\ H(j_1,j_2,\dots ,j_{k-1}-1,j_k),H(j_1,j_2,\dots ,j_{k-1},j_k-1)).\end{array}$$( ∗ )

We use our multipeg algorithm recursively and so can move up to $K(j_1,\dots ,j_{i-1})$ disks back from P_i to L, since at this time disk m is the only disk in $W(j_1,\dots ,j_{i-1})$ and can be moved freely to any work peg. We choose $m_i=\min (j_i,K(j_1,\dots ,j_{i-1}))$ for $1\le i\le k$. Remember here that the parameters for K and H may need sorting again. After these transfers back to L from pegs $P_2,\dots ,P_k$, we have the configuration $〈F_{m-1}^{s+1}|-:\cdots :-:m|C_s〉$, where $s=m-{\sum }_{i=1}^k{m}_i$.

In the fourth stage, we transfer the top $K(j_i,\dots ,j_{k-1},j_k)=m\prime$ disks from R to L reaching configuration $〈C_{m\prime },F_{m-1}^{s+1}|-:\cdots :-:m|F_s^{m\prime +1}〉$ using the same method.

Note that the second and third stages taken together achieve the following,$$〈F_m^{s+1}|-:\cdots :-|C_s〉\Rightarrow 〈F_{m-1}^{s+1}|-:\cdots :-:m|C_s〉,$$extracting disk m from under a stack of $m-s-1$ disks on L. The fifth stage of the algorithm reverses such a sequence in order to insert disk m under the $F_s^{m\prime +1}$ on R. This is possible if $s-m\prime \le m-s-1$, i.e., $m-{\sum }_{i=1}^k{m}_i-m\prime \le {\sum }_{i=1}^k{m}_i-1$. We choose $m=2{\sum }_{i=1}^k{m}_i+m\prime -1$. Then$$〈C_{m\prime },F_{m-1}^{s+1}|-:\cdots :-:m|F_s^{m\prime +1}〉\Rightarrow 〈C_{m\prime },F_{m-1}^{s+1}|-:\cdots :-|F_s^{m\prime +1},m〉.$$

The final stages of the algorithm are smaller versions of previous transfers.$$\begin{array}{c}〈C_{m\prime },F_{m-1}^{s+1}|-:\cdots :-|F_s^{m\prime +1},m〉\Rightarrow 〈F_{m-1}^{s+1}|-:\cdots :-|C_s,m〉\\ \Rightarrow 〈C_{m-1}|-:\cdots :-|m〉\Rightarrow 〈-|-:\cdots :-|C_m〉.\end{array}$$

The last transition is by induction on m.

This algorithm yields the following lower bound for multipeg Hanoi. Recall that if we choose $m=2{\sum }_{i=1}^k{m}_i+m\prime -1$, then m disks can be transferred.

Theorem 14

. For $0<j_1\le j_2\le \cdots \le j_k$, and K as defined above in ( $*$), $$H(j_1,\dots ,j_k)\ge 2\sum _{i=1}^k{m}_i+K(j_1,\dots ,j_k)-1,$$where $m_i=\min (j_i,K(j_1,\dots ,j_{i-1})$ for $1\le i\le k$.

For a general set of work pegs an explicit exact formula seems unlikely, but we can give a special case for which this can be shown.

In Theorem 14 we define $m_i=\min (j_i,K(j_1,\dots ,j_{i-1}))$ for $1\le i\le k$. For $W(j_1,\dots ,j_k)$ we say that( ∗∗ ) $$\mathrm{}\text{peg}\mathrm{}{P}_i\mathrm{}\text{is}\mathrm{}\mathit{tight}\mathrm{}\text{if}\mathrm{}{m}_i=j_i.$$( ∗∗ )

For example, in $W(1,1,2)$, P₃ is tight because $2\le H(0,1)\le K(1,1)$, P₂ is tight because $1\le H(0)=K(1)$, and P₁ is tight because $1\le H()=1$.

For the case where all pegs are tight the recursion becomes$$H(j_1,\dots ,j_k)\ge 2\sum _{i=1}^k{j}_i+K(j_1,\dots ,j_k)-1.$$

Recall that the function K is designed to optimize the position in W of the largest element during a major transfer from L to R. We will see that placing this on P_k achieves optimality when all pegs are tight, so $K(j_1,\dots ,j_k)=H(j_1,\dots ,j_k-1)$. It is then easy to check that all pegs are tight in $W(j_1,\dots ,j_k-1)$, even after any necessary re-sorting.

Now we can verify the lower bound $H(j_1,\dots ,j_k)\ge {({\sum }_{i=1}^k{j}_i)}^2+1$, since$$\begin{array}{c}H(j_1,\dots ,j_k)\ge 2\sum _{i=1}^k{j}_i+H(j_1,\dots ,j_{k-1},j_k-1)-1\\ \ge 2\sum _{i=1}^k{j}_i+{\left(-1+\sum _{i=1}^k{j}_i\right)}^2+1-1={\left(\sum _{i=1}^k{j}_i\right)}^2+1.\end{array}$$

Theorem 6 provides the matching upper bound, giving the following result.

Theorem 15.

If all pegs are tight in $W(j_1,\dots ,j_k)$, i.e., $j_i\le K(j_1,\dots ,j_{i-1})$ for $1\le i\le k$, then $$H(j_1,\dots ,j_k)={\left(\sum _{i=1}^k{j}_i\right)}^2+1.$$

The example $H(0!,1!,\dots ,10!)$, mentioned in our abstract, illustrates this theorem. Here, when $j_i=(i-1)!$, all pegs are tight. As in the example $W(1,1,2)$ above, P₁, P₂, P₃ of heights $0!,1!,2!$, respectively, are tight. So P₄, of height $3!=6$, is also tight, as $H(0!,1!,2!-1)={(0!+1!+2!-1)}^2+1=10$. (Since $2!$ for P₃ is tight, so is $2!-1$.) It is easily seen that this continues for subsequent work pegs.

There is more work to be done for the general case, as the following example shows.

Example 16.

For $W(1,2,3)$, Theorem 14 gives $m_1=m_2=1$ and $m_3=3$, and $H(1,2,3)\ge 10+H(1,2,2)-1=35$. (We assume here that $H(1,2,2)=26$ and will return to this later.) However,the following sequence shows that $H(1,2,3)\ge 37$.$$\begin{array}{c}〈C_{37}|-\mathrm{}:\mathrm{}--\mathrm{}:\mathrm{}---|-〉\Rightarrow 〈F_{37}^{32}|-\mathrm{}:\mathrm{}--\mathrm{}:\mathrm{}---|C_{31}〉\\ \stackrel{\mathit{see}\mathit{below}}{\Rightarrow }〈F_{36}^{32}|-\mathrm{}:\mathrm{}--\mathrm{}:\mathrm{}--37|C_{31}〉\Rightarrow 〈C_{26},F_{36}^{32}|-\mathrm{}:\mathrm{}--\mathrm{}:\mathrm{}--37|F_{31}^{27}〉\\ \stackrel{\mathit{similarly}}{\Rightarrow }〈C_{26},F_{36}^{32}|-\mathrm{}:\mathrm{}--\mathrm{}:\mathrm{}---|F_{31}^{27},37〉\Rightarrow 〈F_{36}^{32}|-\mathrm{}:\mathrm{}--\mathrm{}:\mathrm{}---|C_{31},37〉\\ \Rightarrow 〈C_{36}|-\mathrm{}:\mathrm{}--\mathrm{}:\mathrm{}---|37〉\Rightarrow 〈-|-\mathrm{}:\mathrm{}--\mathrm{}:\mathrm{}---|C_{37}〉.\end{array}$$

We have found some sequences of moves much easier to follow using a reduced notation. The sequence labeled “see below” moves the largest disk to P₃ from under a stack of five disks on L. Peg R is not involved. We denote the initial configuration before this sequence as $\mathit{abcdef}|-\mathrm{}:\mathrm{}--\mathrm{}:\mathrm{}---|〉$, where, as in the proof of Lemma 10, peg R is ignored. The required sequence is then$$\begin{array}{c}〈\mathit{abcdef}|-\mathrm{}:\mathrm{}--\mathrm{}:\mathrm{}---|\Rightarrow 〈-|f\mathrm{}:\mathrm{}de\mathrm{}:\mathrm{}\mathit{abc}|\Rightarrow 〈d|f\mathrm{}:\mathrm{}-e\mathrm{}:\mathrm{}\mathit{abc}|\Rightarrow 〈\mathit{abd}|f\mathrm{}:\mathrm{}-e\mathrm{}:\mathrm{}--c|\\ \Rightarrow 〈\mathit{abd}|-\mathrm{}:\mathrm{}ce\mathrm{}:\mathrm{}--f|\Rightarrow 〈d|-\mathrm{}:\mathrm{}ce\mathrm{}:\mathrm{}\mathit{abf}|\Rightarrow 〈c|d\mathrm{}:\mathrm{}-e\mathrm{}:\mathrm{}\mathit{abf}|\\ \Rightarrow 〈\mathit{abc}|d\mathrm{}:\mathrm{}-e\mathrm{}:\mathrm{}--f|\Rightarrow 〈\mathit{abc}|e\mathrm{}:\mathrm{}-d\mathrm{}:\mathrm{}--f|\Rightarrow 〈-|e\mathrm{}:\mathrm{}cd\mathrm{}:\mathrm{}\mathit{abf}|\\ \Rightarrow 〈\mathit{cde}|-\mathrm{}:\mathrm{}--\mathrm{}:\mathrm{}\mathit{abf}|\Rightarrow 〈\mathit{abcde}|-\mathrm{}:\mathrm{}--\mathrm{}:\mathrm{}--f|.\end{array}$$

The sequence labeled “similarly” moves disk 37 from P₃ to below $F_{31}^{27}$ on R. This is just like the reverse of the sequence that moves 37 from the bottom of $F_{37}^{32}$ to P₃, which we gave in detail above.

In Theorem 14, the biggest disk m moves from P₁ to P₂, then from P₂ and P₃ and so on, one by one, but in the above example m moves from P₁ to P₃ directly. Such a “jump” of the biggest disk also allows us to show that $H(1,2,2)\ge 26$. We can generalize this jumping strategy in the form of an algorithm, but there is unlikely to be a succinct specification of m₁ through m_k based on that. We restrict ourselves therefore to the case of three work pegs and present an algorithm which may be optimal.

Jump algorithm

This algorithm follows a similar scheme to that in Theorem 14 but makes use of the tactic introduced in Example 16 where the largest disk may jump directly from P₁ to P₃. The heart of the algorithm lies in the choice of the values for m₂ and m₃.

The heights of pegs P₁,P₂,P₃ are j₁,j₂,j₃, where $j_1\le j_2\le j_3$, and we describe the transfer of C_m from L to R. As in the algorithm for Theorem 14, in the first stage some suitable cone C_s is transferred recursively from L to R. In the second stage, frusta of sizes m₃, m₂ and m₁ are loaded successively from L onto pegs P₃, P₂, and P₁. We choose $m_1=1$ with two alternatives plans for m₂ and m₃ $$\begin{array}{c}\begin{array}{cccc}\text{either}& \text{Plan}\mathrm{}\left(\mathrm{A}\right),& m_2=j_1,& m_3=\min (j_3,H(j_1,j_2-1)+j_1)\end{array}\\ \begin{array}{cccc}\text{or}& \text{Plan}\mathrm{}\left(\mathrm{B}\right),& m_2=j_1+1,& m_3=\min (j_3,H(j_1-1,j_2-1)+j_1).\end{array}\end{array}$$

We will use the plan that gives the larger value for $m_2+m_3$, though note that Plan (B) is only feasible when $j_2>j_1$. We can verify in this case that the two plans have equal performance if $j_3=2j_1{j}_2+j_2$, while Plan (A) is better when j₃ is greater than this, and worse when less. The parameter s in the first stage is chosen so that $s+m_1+m_2+m_3=m$, and therefore peg L is emptied in the second stage.

Stage 3 now begins to return all disks except for the largest to L. The sequences now become more intricate and we rely on the growing expertise of the reader to interpolate the details. We extend the alphabetic notation introduced in Example 16 to a more advanced level in which lower case letters denote single disks, while upper case letters denote frusta of given sizes.

Plan (A): with $m_1=1$, m₂ = j₁, $m_3=\min (j_3,H(j_1,j_2-1)+j_1)$.

In the first stage,$$〈\mathit{ABCDeFg}|-\mathrm{}:\mathrm{}-\mathrm{}:\mathrm{}-|-〉\Rightarrow 〈\mathit{CDeFg}|-\mathrm{}:\mathrm{}-\mathrm{}:\mathrm{}-|AB〉,$$where $\left|A\right|=K(j_1,j_2,j_3)$ and $B=m_2+m_3$. Now AB remains on R and the second stage is to move g to W from below $C,D,e,F$ on L. Here, $\left|C\right|=\min (H(j_1,j_2-1),j_3-j_1),\left|D\right|=j_1-1$, and $\left|F\right|=j_1$. We see that $\left|\mathit{CDe}\right|=m_3$ as required.

As in Example 16, we will just show the contents of L and the work pegs. Note that in the second sequence F is transferred from P₂ to L using the space $j_1-1$ on P₁, and in the third sequence the transfer of C from P₃ to L is possible since $\left|C\right|\le H(j_1,j_2-1)$.$$\begin{array}{c}〈\mathit{CDeFg}|-\mathrm{}:\mathrm{}-\mathrm{}:\mathrm{}-|\Rightarrow 〈-|g\mathrm{}:\mathrm{}F\mathrm{}:\mathrm{}\mathit{CDe}|\Rightarrow 〈F|-\mathrm{}:\mathrm{}g\mathrm{}:\mathrm{}\mathit{CDe}|\Rightarrow 〈CF|-\mathrm{}:\mathrm{}g\mathrm{}:\mathrm{}De|\\ \Rightarrow 〈CF|De\mathrm{}:\mathrm{}-\mathrm{}:\mathrm{}g|\Rightarrow 〈CF|-\mathrm{}:\mathrm{}e\mathrm{}:\mathrm{}Dg|\Rightarrow 〈F|-\mathrm{}:\mathrm{}e\mathrm{}:\mathrm{}\mathit{CDg}|\\ \Rightarrow 〈eF|-\mathrm{}:\mathrm{}-\mathrm{}:\mathrm{}\mathit{CDg}|\Rightarrow 〈\mathit{CDeF}|-\mathrm{}:\mathrm{}-\mathrm{}:\mathrm{}g|.\end{array}$$

The third stage is to achieve$$〈\mathit{CDeF}|-\mathrm{}:\mathrm{}-\mathrm{}:\mathrm{}g|AB〉\Rightarrow 〈\mathit{ACDeF}|-\mathrm{}:\mathrm{}-\mathrm{}:\mathrm{}g|B〉\Rightarrow 〈\mathit{ACDeF}|-\mathrm{}:\mathrm{}-\mathrm{}:\mathrm{}-|Bg〉,$$i.e., to transfer A back to L, and then to insert g below B on R. Note that $\left|A\right|=K(j_1,j_2,j_3)$, so the transfer of A to L is possible with an appropriate positioning of disk g in W. Since $\left|B\right|=m_2+m_3$, the insertion of g below B has the same pattern as the reversal of the second stage, extracting g from below CDeF. The final stages are just as in the algorithm for Theorem 14, so A moves to R, then AB moves back to L, and the rest is recursion.

Plan (B): with $m_1=1,m_2=j_1+1,m_3=\min (j_3,H(j_1-1,j_2-1)+j_1)$.

This alternative is only available when $j_2>j_1$ and proceeds in a similar way, but with a few more steps.$$〈\mathit{ABCDeFghi}|-\mathrm{}:\mathrm{}-\mathrm{}:\mathrm{}-|-〉\Rightarrow 〈\mathit{CDeFghi}|-\mathrm{}:\mathrm{}-\mathrm{}:\mathrm{}-|AB〉,$$where $\left|A\right|=K(j_1,j_2,j_3),B=m_2+m_3,\left|C\right|=\min (H(j_1-1,j_2-1),j_3-j_1)$, and $\left|D\right|=\left|F\right|=j_1-1$. The size of C is chosen to allow it to be transferred between L and P₃ when P₁ and P₂ each hold a single disk. Now$$\begin{array}{c}〈\mathit{CDeFghi}|-\mathrm{}:\mathrm{}-\mathrm{}:\mathrm{}-|\Rightarrow 〈-|i\mathrm{}:\mathrm{}\mathit{Fgh}\mathrm{}:\mathrm{}\mathit{CDe}|\Rightarrow 〈\mathit{CFg}|i\mathrm{}:\mathrm{}h\mathrm{}:\mathrm{}De|\\ \Rightarrow 〈\mathit{CFg}|-\mathrm{}:\mathrm{}\mathit{Deh}\mathrm{}:\mathrm{}i|\Rightarrow 〈\mathit{CFg}|e\mathrm{}:\mathrm{}h\mathrm{}:\mathrm{}Di|\Rightarrow 〈Fg|e\mathrm{}:\mathrm{}h\mathrm{}:\mathrm{}\mathit{CDi}|\\ \Rightarrow 〈g|e\mathrm{}:\mathrm{}Fh\mathrm{}:\mathrm{}\mathit{CDi}|\Rightarrow 〈-|g\mathrm{}:\mathrm{}\mathit{eFh}\mathrm{}:\mathrm{}\mathit{CDi}|\Rightarrow 〈\mathit{CeF}|g\mathrm{}:\mathrm{}h\mathrm{}:\mathrm{}Di|\\ \Rightarrow 〈\mathit{CeF}|-\mathrm{}:\mathrm{}h\mathrm{}:\mathrm{}\mathit{Dgi}|\Rightarrow 〈\mathit{CeF}|h\mathrm{}:\mathrm{}g\mathrm{}:\mathrm{}Di|\Rightarrow 〈eF|h\mathrm{}:\mathrm{}g\mathrm{}:\mathrm{}\mathit{CDi}|\\ \Rightarrow 〈h|-\mathrm{}:\mathrm{}\mathit{eFg}\mathrm{}:\mathrm{}\mathit{CDi}|\Rightarrow 〈\mathit{CDeFgh}|-\mathrm{}:\mathrm{}-\mathrm{}:\mathrm{}i|.\end{array}$$

The last stages are the same as for Plan (A).

Theorem 17.

For $j_1\le j_2\le j_3$, let $$\begin{array}{c}{m}_A=1+j_1+\min (j_3,H(j_1,j_2-1)+j_1)\text{and}\\ m_B=1+\min (j_2,j_1+1)+\min (j_3,H(j_1-1,j_2-1)+j_1).\end{array}$$

Then $H(j_1,j_2,j_3)\ge 2\max (m_A,m_B)+K(j_1,j_2,j_3)-1$.

Proof.

In Plan (A), m₂ = j₁ and $m_3=\min (j_3,H(j_1,j_2-1)+j_1)$, so $m_1+m_2+m_3=m_A$, and C_m is transferred from L to R where$$m=\left|\mathit{ABCDeFg}\right|=K(j_1,j_2,j_3)+(m_A-1)+m_A,$$as required.

In Plan (B), $m_2=j_1+1=\min (j_2,j_1+1)$ and $m_3=\min (j_3,H(j_1-1,j_2-1)+j_1)$, so $m_1+m_2+m_3=m_B$, and$$m=\left|\mathit{ABCDeFghi}\right|=K(j_1,j_2,j_3)+(m_B-1)+m_B.\mathrm{}$$

■

Theorem 17 yields the promised bound of $H(1,2,2)=26$, the example illustrated in Figure 1. The upper bound is given by Theorem 6. Plan (B) uses $(m_1,m_2,m_3)=(1,2,2)$ for a matching lower bound of $10+K(1,2,2)-1=26$, since $K(1,2,2)=H(1,1,2)=17$.

Fig. 1 A tower of 26 disks being transferred using work pegs of heights 2, 1, and 2.

Theorems 12, 14, and 17 give successive improvements to the lower bounds, but at the cost of more complicated algorithms. How much do these extra complications buy for us? As a rough indication, we show below a comparison of $H_1(j,j,j),H_2(j,j,j)$, and $H_3(j,j,j)$, for the results of Theorems 12, 14, and 17, respectively.

7 Conclusion

We have begun an investigation into the space complexity of the generalized Tower of Hanoi problem, where the number of work pegs provided to transfer a set of disks from the initial peg to the final peg is increased from the single peg used in the classic problem.

We pay little attention to the time complexity, the number of moves, in our algorithms. As may be expected from even our first example, transferring five disks using two unit pegs and 25 moves, the time complexity is large compared with that for unbounded pegs, where only 13 moves are needed. Lemma 7 shows that 25 disks can be transferred using two work pegs of height three. With unbounded pegs this requires precisely 577 moves [5], but our algorithm takes over 2,000,000 moves, as estimated by a simple Mathematica program. It remains to be seen whether there are interesting trade-offs between time complexity and space complexity results for Hanoi problems.

We have exact results for $H(j_1,\dots ,j_k)$ when $k\le 2$, for $HU(k)$, i.e., k pegs of height 1, and for the case where all the pegs are tight (defined in ($**$) in the previous section). Theorem 14 gives a fairly close bound for $H(j_1,\dots ,j_k)$, but we know this is not exact. Indeed, Theorem 17 gives better lower bounds in the case of k = 3, and the algorithm given there could even be optimal.

There are some very small cases for the general problem where gaps remain. By ad hoc methods, we know exact values for all cases where the total work space is at most six. However, Theorem 17 shows only that $H(1,3,3)\ge 48$, while our best upper bound so far invokes Theorem 6 to prove that $H(1,3,3)\le HU(7)=50$. Surely this gap can be closed!

Table 1 Lower bounds for $H(j,j,j)$ from Theorems 12, 14, and 17.

Peg height $j=$	1	2	3	4	5	6	7	8	9	10
$H_1(j,j,j)$ (Thm.12)	10	31	64	109	166	235	316	409	514	631
$H_2(j,j,j)$ (Thm.14)	10	33	68	117	180	257	348	453	570	701
$H_3(j,j,j)$ (Thm.17)	10	35	74	125	190	269	362	469	590	725

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.