A new lower bound for the Towers of Hanoi problem (Q2635086)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A new lower bound for the Towers of Hanoi problem |
scientific article |
Statements
A new lower bound for the Towers of Hanoi problem (English)
0 references
11 February 2016
0 references
Summary: More than a century after its proposal, the Towers of Hanoi puzzle with 4 pegs was solved by \textit{T. Bousch} in a breakthrough paper [Bull. Belg. Math. Soc. - Simon Stevin 21, No. 5, 895--912 (2014; Zbl 1307.05006)]. The general problem with \(p\) pegs is still open, with the best lower bound on the minimum number of moves due to \textit{X. Chen} and \textit{J. Shen} [SIAM J. Comput. 33, No. 3, 584--589 (2004; Zbl 1055.05002)]. We use some of Bousch's new ideas to obtain an asymptotic improvement on this bound for all \(p \geqslant 5\).
0 references
Towers of Hanoi
0 references
shortest paths
0 references