The Library
Bounded Hanoi
Tools
Tools
Tools
Iwama, Kazuo and Paterson, Mike (2022) Bounded Hanoi. The American Mathematical Monthly, 129 (4). pp. 303-319. doi:10.1080/00029890.2022.2026166 ISSN 1930-0972.
|
PDF
WRAP-Bounded-Hanoi-22.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (730Kb) | Preview |
Official URL: https://doi.org/10.1080/00029890.2022.2026166
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 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).
| Item Type: | Journal Article | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
|||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||
| SWORD Depositor: | Library Publications Router | |||||||||
| Library of Congress Subject Headings (LCSH): | Mathematical recreations , Computer algorithms , Computer software., Sequences (Mathematics), Combinatorial analysis, Graph theory | |||||||||
| Journal or Publication Title: | The American Mathematical Monthly | |||||||||
| Publisher: | Informa UK Limited | |||||||||
| ISSN: | 1930-0972 | |||||||||
| Official Date: | 29 March 2022 | |||||||||
| Dates: |
|
|||||||||
| Volume: | 129 | |||||||||
| Number: | 4 | |||||||||
| Page Range: | pp. 303-319 | |||||||||
| DOI: | 10.1080/00029890.2022.2026166 | |||||||||
| Status: | Peer Reviewed | |||||||||
| Publication Status: | Published | |||||||||
| Access rights to Published version: | Open Access (Creative Commons) | |||||||||
| Date of first compliant deposit: | 16 November 2022 | |||||||||
| Date of first compliant Open Access: | 16 November 2022 | |||||||||
| RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
