On the Optimal General Solution to the Multi-Peg Tower of Hanoi
Abhiram Menon · 2025
Read On the Optimal General Solution to the Multi-Peg Tower of Hanoi by Abhiram Menon (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-12941.txt.
Introduction
Abhiram Menon, writing alone in 2025, solves a classic puzzle in general form. The Tower of Hanoi asks for the fewest moves to shift a stack of disks between pegs, and extra pegs cut the count sharply. A standard method gives the count step by step, but no single formula covered all peg and disk counts.
Menon derives one closed formula for that method and proves it fits the step rule for every case. Within each regime the count grows in straight lines, with slopes doubling at each boundary. He also proves the method is truly best for the first two regimes, covering endless pairs of peg and disk counts. That settles a long-standing guess up to a stated bound.
Catalog record
| CREATOR | Abhiram Menon |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 36 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-12941
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the Optimal General Solution to the Multi-Peg Tower of Hanoi Abhiram Menon Abstract We derive a closed-form expression for the Frame–Stewart algorithm in the multi-peg Tower of Hanoi problem: M ( p , n ) = 2 i ( p , n ) + 1 n − ∑ k = 0 i ( p , n ) 2 k ( p + k − 2 k ) , M(p,n)=2^{i(p,n)+1}n-\sum_{k=0}^{i(p,n)}2^{k}\binom{p+k-2}{k}, where i ( p , n ) = min { j ≥ 0 : n ≤ ( p − 1 + j j + 1 ) } i(p,n)=\min\{j\geq 0:n\leq\binom{p-1+j}{j+1}\} is the regime index. We prove this expression satisfies the Frame–Stewart recurrence for all p ≥ 3 p\geq 3 and n ≥ 1 n\geq 1 via double induction based on discrete slope analysis and canonical splits at simplex number boundaries. The representation enables O ( p log n ) O(p\log n) evaluation and makes the geometric structure explicit. Beyond the recurrence equivalence, we prove that Frame–Stewart is optimal for the first two regimes. For regime 1 ( p − 1 < n ≤ ( p 2 ) p-1<n\leq\binom{p}{2} ), we establish M ( p , n ) = 4 n − 2 p + 1 M(p,n)=4n-2p+1 via phase-based charging with a borrowed-target construction. For regime 2 ( ( p 2 ) < n ≤ ( p + 1 3 ) \binom{p}{2}<n\leq\binom{p+1}{3} ), we prove M ( p , n ) = 8 n − 2 p 2 + 1 M(p,n)=8n-2p^{2}+1 using a two-layer charging argument and convexity-based capacity bounds on auxiliary configurations. These results provide complete proofs of Frame–Stewart optimality for an infinite family of ( p , n ) (p,n) pairs beyond the trivial case n ≤ p − 1 n\leq p-1 . The general conjecture for regimes i ≥ 3 i\geq 3 remains open. 1 Introduction The Tower of Hanoi is one of the best-known puzzles in mathematics. In the classical version with three pegs, introduced by Édouard Lucas in 1883, the exact number of moves is 2^{n}-1 , a result known since the nineteenth century. The puzzle asks for the fewest moves needed to transfer a stack of n ordered disks between pegs, moving one disk at a time and never placing a larger disk on top of a smaller one. In 1941, Frame and Stewart proposed a natural recursive strategy for more than three pegs, but proving that their method is truly optimal has resisted resolution ever since. The so-called Frame–Stewart conjecture has remained open for over eighty years. There has been progress in special cases. The case p=3 is classical. The case p=4 was finally solved by Bousch [ 4 ] , after decades of attempts. Some small n cases relative to p were settled earlier, and computational work has supported the conjecture more broadly. But a general proof remains elusive; see [ 5 ] for background. This paper makes progress on two fronts. First, we derive a closed-form expression that satisfies the Frame–Stewart recurrence exactly for all (p,n) . While this demonstrates the internal consistency of Frame–Stewart’s values, it does not by itself prove optimality. Second, we prove that Frame–Stewart is indeed optimal in the first two linear regimes: regime 1 where p-1<n\leq\binom{p}{2} with M(p,n)=4n-2p+1 , and regime 2 where \binom{p}{2}<n\leq\binom{p+1}{3} with M(p,n)=8n-2p^{2}+1 . This covers infinitely many pairs (p,n) and represents genuine progress on the conjecture beyond trivial cases. The main tools are phase-based charging arguments that measure how disks must be distributed during evacuation and reassembly. For regime 1, a single-layer charge suffices. For regime 2, we develop a two-layer charging scheme combined with convexity-based capacity bounds on the auxiliary configuration space. 2 Preliminaries Definition 1 (Tower of Hanoi) . The Tower of Hanoi with p\geq 3 pegs and n\geq 1 disks requires transferring all n disks from a source peg S to a target peg T , one disk at a time, never placing a larger disk on top of a smaller disk. Let M(p,n) be the minimum number of moves needed. Definition 2 (Frame–Stewart Algorithm) . The Frame–Stewart algorithm works as follows. Given p pegs and n disks: (i) Pick k\in\{1,2,\dots,n-1\} to minimize 2M(p,k)+M(p-1,n-k) . (ii) Move the top k disks to a spare peg using all p pegs. (iii) Move the remaining n-k disks to the target using p-1 pegs. (iv) Move the k disks from the spare peg to the target using all p pegs. The Frame–Stewart recurrence is defined by M_{\mathrm{FS}}(p,n)=\begin{cases}0,&n=0,\\ 1,&n=1,\\ \displaystyle\min_{1\leq t<n}\{2M_{\mathrm{FS}}(p,t)+M_{\mathrm{FS}}(p-1,n-t)\},&n\geq 2,\end{cases} (1) with M_{\mathrm{FS}}(3,n)=2^{n}-1 . The conjecture states this strategy is optimal for all p\geq 3 and n\geq 1 . 3 Three Linear Windows and Boundaries Direct tabulation of M_{\mathrm{FS}}(p,n) for fixed p reveals a piecewise-linear profile in n : the discrete slope is constant on contiguous intervals and doubles whenever n crosses a canonical breakpoint. On the first interval, where the number of available auxiliaries is at least n-1 , one obtains M(p,n)=2n-1\qquad(1\leq n\leq p-1). (2) Immediately beyond n=p-1 the slope doubles to 4 and remains constant up to the triangular boundary n=\binom{p}{2} . Enforcing continuity at the endpoints fixes the intercept and yields M(p,n)=4n-(2p-1)\qquad(p-1<n\leq\binom{p}{2}). (3) At the triangular boundary n=\binom{p}{2} the slope doubles again, becoming 8 on the next interval. Continuity at n=\binom{p}{2} pins down the new intercept uniquely: 4n-(2p-1)\Big|_{n=\binom{p}{2}}=2p(p-1)-2p+1=8n+C_{3}\Big|_{n=\binom{p}{2}}=4p(p-1)+C_{3}, so C_{3}=-2p^{2}+1 and therefore M(p,n)=8n-2p^{2}+1\qquad(\binom{p}{2}<n\leq\binom{p+1}{3}). (4) These three windows already exhibit the governing pattern: constant slopes 2, 4, 8 on successive intervals, with clean breakpoints at the triangular and tetrahedral numbers. The table below summarizes the first three ranges and their explicit formulas. Interval in n Slope of M(p,\cdot) Closed form 0\leq n\leq p-1 2 M(p,n)=2n-1 p-1<n\leq\binom{p}{2} 4 M(p,n)=4n-(2p-1) \binom{p}{2}<n\leq\binom{p+1}{3} 8 M(p,n)=8n-2p^{2}+1 The pattern strongly suggests that the breakpoints are the (p-1) -simplex numbers and that the slope doubles each time we cross to the next simplex layer. 4 Simplex Boundaries and the Unified Closed Form As the three linear windows indicate, the solution is captured by the single formula: M(p,n)=2^{i+1}n-\sum_{k=0}^{i}2^{k}\binom{p+k-2}{k},\quad i=\min\{j\geq 0:n\leq\binom{p-1+j}{j+1}\}. (5) The integer i determined by ( 5 ) is the regime index : it records which simplex layer contains n . When i=0 the range is 0\leq n\leq p-1 and ( 5 ) yields M(p,n)=2n-1 ; when i=1 the range is p-1<n\leq\binom{p}{2} and the same expression reduces to M(p,n)=4n-(2p-1) . Larger i continue the same linear pattern with slopes 2^{i+1} . For bookkeeping, it is convenient to isolate the cut points themselves. We therefore introduce the boundary sequence B_{p}(i):=\binom{p-1+i}{i+1}\quad(i\geq 0),\qquad B_{p}(-1):=0, (6) so that the i th regime is precisely B_{p}(i-1)<n\leq B_{p}(i) . With this notation the regime index can be written explicitly as a function of (p,n) : i(p,n):=\min\{j\geq 0:n\leq B_{p}(j)\}, (7) which is identical to the i appearing in ( 5 ). The boundaries satisfy the Pascal decomposition B_{p}(i)=B_{p-1}(i)+B_{p}(i-1)\qquad(i\geq 0), (8) encoding the well-known relation between consecutive simplex numbers (triangular, tetrahedral, etc.). Rewriting ( 5 ) with the explicit dependence i=i(p,n) we arrive at the form used throughout the remainder of the paper: M(p,n)=2^{i(p,n)+1}n-\sum_{k=0}^{i(p,n)}2^{k}\binom{p+k-2}{k}. (9) It is helpful to abbreviate by S_{p}(i):=\sum_{k=0}^{i}2^{k}\binom{p+k-2}{k},\qquad S_{p}(-1):=0, (10) so that ( 9 ) reads M(p,n)=2^{i(p,n)+1}n-S_{p}(i(p,n)) . The interpretation is immediate: within the regime indexed