Séminaire Lotharingien de Combinatoire, B77d (2017), 30 pp.
Thierry Bousch
La Tour de Stockmeyer
Abstract.
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
2S1(N) moves,
where S1(N)
denotes the sum of the smallest N integers of the
form 2a3b,
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 2S1(N) mouvements,
où S1(N) désigne la somme
des N plus petits entiers de la forme
2a3b, et conjecturé que
ce nombre ne pouvait être diminué. C'est ce que
je démontre
dans le présent article.
Received: December 6, 2016.
Revised: April 13, 2017.
Accepted: April 17, 2017.
The following versions are available: