Dan Romik (Weizmann I.)

will speak on

Shortest paths in the Tower of Hanoi graph and finite automata.

Abstract:

I will describe the problem of shortest paths in the Tower of Hanoi graph, i.e. shortest sequences of moves in the Tower of Hanoi puzzle leading from one legal disc configuration to another. The well-known special case of moving all the discs from one peg to another is an easy example, but the general case of arbitrary initial and terminal positions leads to an interesting algorithmic design problem. My recent solution involves the construction of a "tiebreaker" finite automaton that determines whether the largest disc will move once, or twice. As an application, I will calculate the average distance 466/885 between two randomly chosen points on the Sierpinski gasket (a.k.a. Sierpinski triangle) of unit side.

To suggest a talk (yours, or someone elses), contact Jon. Aaronson:

Back to: Jon Aaronson's homepage.

Last update on 20/10/02.