4 problems

Frame–Stewart conjecture. This recurrence equals the true optimum for every $n$. The conjecture asserts optimality of the standard divide-and-conquer strategy for the four-peg Towe…

Let $p\geq 3$, let $G^{(p)}_{n+1}$ contain the copy $AG^{(p)}_n$, and let $S_{n_0}$ be the recursively defined border set. Let $a$ be the vertex labeled $A^{n_0+1}$, and call a ver…

Let $G^{(p)}_n$ be the recursively defined Tower of Hanoi graph, and let $S_n$ be the border set of the copy $AG^{(p)}_n$ in $G^{(p)}_{n+1}$. A shortest path from $a$ to a vertex o…

Let $p\geq 3$, let ${\cal A}_p$ be an alphabet of $p$ letters, and let $A,B\in{\cal A}_p$. For $n\geq 2$, consider vertices labeled $A^n$ and $B^n$. A vertex on a path is special i…