La Tour de Stockmeyer

Thierry Bousch

Séminaire lotharingien de combinatoire, Tome 77 (2017-2018)

Résumé

In 1994, Paul Stockmeyer proposed a four-peg variant of the Tower of Hanoi puzzle, with three exterior pegs surrounding a central peg, and the restriction that disks can only be moved between an exterior peg and the central peg. He proved that it is possible to transfer N disks from an exterior peg to another with 2S₁(N) moves, where S₁(N) denotes the sum of the smallest N integers of the form 2^a3^b, and conjectured that this number could not be decreased. This is proved in the present article.

Résumé. En 1994, Paul Stockmeyer a proposé une variante à quatre tiges de la Tour d'Hanoï, avec trois tiges extérieures disposées en étoile autour d'une tige centrale, et la restriction qu'on ne peut déplacer les disques qu'entre une tige extérieure et la tige centrale. Il a démontré qu'on peut transférer N disques d'une tige extérieure vers une autre en 2S₁(N) mouvements, où S₁(N) désigne la somme des N plus petits entiers de la forme 2^a3^b, et conjecturé que ce nombre ne pouvait être diminué. C'est ce que je démontre dans le présent article.