Date: Tuesday, 7 Adar 5766 (March 7, '06)

Speaker: Shay Solomon (Ben-Gurion University)

Title: "A Solution of the $k$-Relaxed Tower of Hanoi Problem"

Abstract:
---------

We study the $k$-Relaxed Tower of Hanoi Problem $RTH_k(n)$, posed by
Wood
in 1981. It differs from the classical problem by the relaxed
placement
rule: a bigger disk can be placed above a smaller disk if their sizes
differ by less than $k$. The shortest sequence of moves from the
standard
state of disks $[1..n]$ on peg A to that on peg C, using peg B, is in
question. For $k=1$ we get the classic problem.

In 1992, Poole suggested a solution for this problem, which now is
known
to have a fundamental gap. Beneditkis, Berend, and Safro suggested in
1998 a sequence of moves, denoted by $\AA_k(n)$, and for the case
$k=2$
proved its optimality for $RTH_k(n)$.

We prove optimality of $\AA_k(n)$ for $RTH_k(n)$, for the general
$k$.
(Interestingly, a proof of optimality of $\AA_n$ for $RTH_n$ was
suggested independently by Xiaomin Chen et al., approximately at
the same
time.)

We also survey some related problems:
1. Finding an optimal move sequence for $RTH_k(n)$, when allowing the
   sizes of the $n$ disks be any set of $n$ distinct integers.
2. Finding the diameter of the graph of all configurations of $RTH_k(n)$.
3. Finding the family of all optimal solutions for $RTH_k(n)$.