In How Many Steps the k Peg Version of the Towers of Hanoi Game Can Be Solved?

Mario SzegedySTACS 1999 · OpenReview

Abstract

In this we paper we consider the version of the classical Towers of Hanoi games where the game-board contains more than three pegs. For k pegs we give a \( 2^{C_k ^{n^{1/(k - 2)} } } \) lower bound on the number of steps necessary for transferring n disks from one peg to another. Apart from the value of the constants C k this bound is tight.
BibTeX
@inproceedings{szegedy1999how,
  author = {Mario Szegedy},
  title = {{In How Many Steps the k Peg Version of the Towers of Hanoi Game Can Be Solved?}},
  booktitle = {STACS},
  year = {1999},
  url = {https://openreview.net/forum?id=4ttjEqT44X},
}

Loading related content...

Figure