Back to Search
Start Over
The Dudeney–Stockmeyer Conjecture
- Source :
- Discrete Applied Mathematics. 319:19-26
- Publication Year :
- 2022
- Publisher :
- Elsevier BV, 2022.
-
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 ∈ N discs from one peg to another according to the well-known rules of the classical game corresponding to D ≅ 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 H D n . 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.
- Subjects :
- Conjecture
Applied Mathematics
0211 other engineering and technologies
Integer sequence
021107 urban & regional planning
0102 computer and information sciences
02 engineering and technology
State (functional analysis)
01 natural sciences
Tower (mathematics)
Task (project management)
Combinatorics
Transfer (group theory)
010201 computation theory & mathematics
Metric (mathematics)
Discrete Mathematics and Combinatorics
Path graph
MathematicsofComputing_DISCRETEMATHEMATICS
Mathematics
Subjects
Details
- ISSN :
- 0166218X
- Volume :
- 319
- Database :
- OpenAIRE
- Journal :
- Discrete Applied Mathematics
- Accession number :
- edsair.doi...........d52b0891552510b2300bdf06af77ff9e