4
$\begingroup$

The Hanoi graph $H^n_k$ is the graph with nodes representing states of a Hanoi puzzle with $n$ discs and $k$ pegs, and edges representing the various moves of the discs from peg to peg.

WIkipeda's Hanoi graph

The Hanoi graph for $H_3^7$ is reproduced above. For $n=3$ there's certainly some similarity to Sierpiński's triangle.

My main question is - if each edge has a $1\:\Omega$ resistor, I'm wondering what we can say about the resistance metric between (say) one vertex of the triangle and another vertex of the triangle?

I'm actually secretly interested in how badly a random walk would proceed on such a graph. Even with an intelligent recursive algorithm it famously takes exponential time to "solve" the puzzle - does an unguided random walk take doubly exponential time?

I bet that, for a fixed $k$, the spectral gap might actually closes with $n$. We'd just be looping around in cycles and taking forever to move the $k$ discs from one peg to the other.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
5
$\begingroup$

No, solutions with random moves are not doubly-exponential on average. Please see my paper Solving the Tower of Hanoi with Random Moves for details. In Section 4, it discusses the resistors approach.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Very nice! My double-secret motivation is whether a quantum walk could do any faster. $\endgroup$
    – Mark S
    Commented Oct 12 at 22:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .