Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2505.12941 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911198078828544 |
|---|---|
| author | Menon, Abhiram |
| author_facet | Menon, Abhiram |
| contents | We derive a unified closed-form expression for the Frame-Stewart algorithm in the multi-peg Tower of Hanoi: M(p,n) = 2^(i(p,n)+1)*n - sum_{k=0}^{i(p,n)} 2^k * C(p+k-2, k), where i(p,n) = min{ j >= 0 : n <= C(p-1+j, j+1) }.
and prove it satisfies the Frame-Stewart recurrence for all (p,n) via double induction using discrete slope analysis with simplex boundaries. It shows that M(p,n) grows linearly within each regime, with slopes doubling at successive boundaries. We also prove Frame-Stewart optimality for the first two regimes indexed by i: for p-1 < n <= C(p,2), M(p,n) = 4n - 2p + 1; for C(p,2) < n <= C(p+1,3), M(p,n) = 8n - 2p^2 + 1. These results give optimality proofs for infinitely many (p,n) pairs beyond trivial cases, settling the conjecture up to n <= C(p+1,3). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_12941 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On The Optimal General Solution To The Multi-Peg Tower of Hanoi Menon, Abhiram Combinatorics 05A20 (Primary) 68Q25, 68R05 (Secondary) G.2; I.5 We derive a unified closed-form expression for the Frame-Stewart algorithm in the multi-peg Tower of Hanoi: M(p,n) = 2^(i(p,n)+1)*n - sum_{k=0}^{i(p,n)} 2^k * C(p+k-2, k), where i(p,n) = min{ j >= 0 : n <= C(p-1+j, j+1) }. and prove it satisfies the Frame-Stewart recurrence for all (p,n) via double induction using discrete slope analysis with simplex boundaries. It shows that M(p,n) grows linearly within each regime, with slopes doubling at successive boundaries. We also prove Frame-Stewart optimality for the first two regimes indexed by i: for p-1 < n <= C(p,2), M(p,n) = 4n - 2p + 1; for C(p,2) < n <= C(p+1,3), M(p,n) = 8n - 2p^2 + 1. These results give optimality proofs for infinitely many (p,n) pairs beyond trivial cases, settling the conjecture up to n <= C(p+1,3). |
| title | On The Optimal General Solution To The Multi-Peg Tower of Hanoi |
| topic | Combinatorics 05A20 (Primary) 68Q25, 68R05 (Secondary) G.2; I.5 |
| url | https://arxiv.org/abs/2505.12941 |