A new lower bound for the Towers of Hanoi problem (Q2635086)

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\).