Self Similarities of the Tower of Hanoi Graphs and a proof of the Frame-Stewart Conjecture

2016/01/17 by Janez Žerovnik, Žerovnik, Janez
Mathematics · #05C99 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C99

paper · pdf · doi:10.48550/arxiv.1601.04298

arxiv created 2016/01/17 · arxiv updated 2016/01/19

Abstract

Considering the symmetries and self similarity properties of the corresponding labeled graphs, it is shown that the minimal number of moves in the Tower of Hanoi game with p =4 pegs and n ≥ p disks satisfies the recursive formula F(p,n) = min_{1≤ i ≤ n-1} \ 2F(p,i) + F(p-1,n-i) \ which proves the strong Frame-Stewart conjecture for the case p=4. The method can be generalized to p>4.

Related

• On the Frame-Stewart Conjecture
• What is the least number of moves needed to solve the k-peg Towers of Hanoi problem?
• On the expansion of Hanoi graphs
• On the Footsteps to Generalized Tower of Hanoi Strategy
• The Parity-Constrained Four-Peg Tower of Hanoi Problem and Its Associated Graph