The Dudeney-Stockmeyer Conjecture

Hinz, Andreas M.; Luzar, Borut und Petr, Ciril (2022): The Dudeney-Stockmeyer Conjecture. In: Discrete Applied Mathematics, Bd. 319: S. 19-26

Abstract

Consider a variant of the famous Tower of Hanoi problem where moves of the discs are allowed along the edges of a connected simple graph D whose vertices represent the vertical pegs of the puzzle. The task is to transfer a tower of n is an element of N discs from one peg to another according to the well-known rules of the classical game corresponding to D expressionpproximexpressiontely equexpressionl to K-3. Apart from its recreational appeal, the problem brings about fascinating integer sequences engendered by the respective minimum number of moves, i.e. the distance in the canonical metric of the state graph HDn. We construct an algorithm which solves the task for all cases but the exceptional instance of the Linear Tower of Hanoi (i.e. where D is a path graph) in which the transfer is between the two end vertices of D. Optimality of this algorithm is claimed in our central conjecture which is supported by large-scale computational explorations. (C) 2021 Elsevier B.V. All rights reserved.

• Dokumententyp: Zeitschriftenartikel
• Fakultät: Mathematik, Informatik und Statistik > Mathematik
• Themengebiete: 500 Naturwissenschaften und Mathematik > 510 Mathematik
• ISSN: 0166-218X
• Sprache: Englisch