The Tower of Hanoi: Optimality Proofs, Multi-Peg Bounds, and Computational Frontiers
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909896778186752 |
|---|---|
| author | Junyi, Qi |
| author_facet | Junyi, Qi |
| contents | The Tower of Hanoi continues to provide a surprisingly rich meeting point for recursive reasoning, combinatorial geometry, and computational verification. Motivated by the editorial standards of the Bulletin of the Australian Mathematical Society, we revisit the classical three-peg problem through Sierpinski-style self-similarity, bring Stockmeyer's uniqueness argument into a modern invariant-based framework, and then pivot to four pegs via the Frame-Stewart strategy and Bousch's optimality proof. The heart of this note is a cautionary data-and-proof cycle: the balanced split k = floor(n/2) is indeed optimal for n <= 8, but our corrected tables show that it already exceeds the optimal cost by 20% at n = 9, crosses the 1.5 mark at n = 13, and comes close to quadrupling the optimum by n = 20. We complement this diagnosis with a subtower-independence lemma, a reproducible table for n <= 15, three publication-ready TikZ figures (recursion arrow, four-peg state diagram, and multi-peg growth curves), and a bibliography exceeding thirty sources that foreground Bulletin and Gazette contributions. The concluding section reframes the open problems as robustness tests for heuristics rather than premature theorems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_07501 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Tower of Hanoi: Optimality Proofs, Multi-Peg Bounds, and Computational Frontiers Junyi, Qi Combinatorics 05A99, 68Q25 F.2.2 The Tower of Hanoi continues to provide a surprisingly rich meeting point for recursive reasoning, combinatorial geometry, and computational verification. Motivated by the editorial standards of the Bulletin of the Australian Mathematical Society, we revisit the classical three-peg problem through Sierpinski-style self-similarity, bring Stockmeyer's uniqueness argument into a modern invariant-based framework, and then pivot to four pegs via the Frame-Stewart strategy and Bousch's optimality proof. The heart of this note is a cautionary data-and-proof cycle: the balanced split k = floor(n/2) is indeed optimal for n <= 8, but our corrected tables show that it already exceeds the optimal cost by 20% at n = 9, crosses the 1.5 mark at n = 13, and comes close to quadrupling the optimum by n = 20. We complement this diagnosis with a subtower-independence lemma, a reproducible table for n <= 15, three publication-ready TikZ figures (recursion arrow, four-peg state diagram, and multi-peg growth curves), and a bibliography exceeding thirty sources that foreground Bulletin and Gazette contributions. The concluding section reframes the open problems as robustness tests for heuristics rather than premature theorems. |
| title | The Tower of Hanoi: Optimality Proofs, Multi-Peg Bounds, and Computational Frontiers |
| topic | Combinatorics 05A99, 68Q25 F.2.2 |
| url | https://arxiv.org/abs/2511.07501 |