• Calendar

March 27, Tuesday
12:00 – 14:00

We study the $k$-Relaxed Tower of Hanoi Problem $BTH_k(n)$, posed by D. Wood in 1981. It differs from the classical problem by the relaxed placement rule: a larger disk can be placed above a smaller one if their size difference is 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 classical problem.

In 1992, D. Poole suggested a solution for this problem, which is now 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 $BTH_k(n)$.

We prove optimality of $\AA_k(n)$ for $BTH_k(n)$, for the general $k$. (Interestingly, a proof of optimality of $\AA_n$ for $BTH_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 $BTH_k(n)$, when allowing the sizes of the $n$ disks be any set of $n$ distinct integers. 2.a Finding the diameter of the configuration graph of $BTH_k(n)$. 2.b Finding the average distance between nodes in the configuration graph of $BTH_k(n)$. 3. Finding the family of all optimal solutions for $BTH_k(n)$ and their number.

If time permits, we would survey some related open problems.
In joint work with Yefim Dinitz.