Twin towers of Hanoi

DOI10.1016/J.EJC.2012.03.026zbMATH Open1254.90287arXiv1108.4494OpenAlexW2074673087MaRDI QIDQ444425FDOQ444425

Authors: Zoran Šunić 

Publication date: 14 August 2012

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: In the Twin Towers of Hanoi version of the well known Towers of Hanoi Problem there are two coupled sets of pegs. In each move, one chooses a pair of pegs in one of the sets and performs the only possible legal transfer of a disk between the chosen pegs (the smallest disk from one of the pegs is moved to the other peg), but also, simultaneously, between the corresponding pair of pegs in the coupled set (thus the same sequence of moves is always used in both sets). We provide upper and lower bounds on the length of the optimal solutions to problems of the following type. Given an initial and a final position of N disks in each of the coupled sets, what is the smallest number of moves needed to simultaneously obtain the final position from the initial one in each set? Our analysis is based on the use of a group, called Hanoi Towers group, of rooted ternary tree automorphisms, which models the original problem in such a way that the configurations on N disks are the vertices at level N of the tree and the action of the generators of the group represents the three possible moves between the three pegs. The twin version of the problem is analyzed by considering the action of Hanoi Towers group on pairs of vertices.

Full work available at URL: https://arxiv.org/abs/1108.4494

Recommendations

• The Group of Symmetries of the Tower of Hanoi Graph
• The Tower of Hanoi with Forbidden Moves
• Tours de Hanoï et automates
• A statistical analysis of the towers of hanoi problem
• scientific article; zbMATH DE number 4008422

zbMATH Keywords

Hanoi Towers grouprooted ternary tree automorphism

Mathematics Subject Classification ID

Dynamic programming (90C39) Exact enumeration problems, generating functions (05A15)

Cites Work

• Shortest Paths in the Tower of Hanoi Graph and Finite Automata
• Title not available (Why is that?)
• The tower of Hanoi
• Self-similar groups and finite Gelfand pairs.
• Asymptotic aspects of Schreier graphs and Hanoi Towers groups.
• Self-similarity and branching in group theory.
• Schreier spectrum of the Hanoi Towers group on three pegs

Cited In (4)

• Schreier spectrum of the Hanoi Towers group on three pegs
• Title not available (Why is that?)
• Traversal languages capturing isomorphism classes of Sierpiński gaskets
• The word problem in Hanoi Towers groups.

This page was built for publication: Twin towers of Hanoi

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q444425)