[Hanoi Tower Troubles Again](https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1217) is a problem I recently discovered in "Programming Challenges" by Skiena and Revilla. It seems to be quite popular, because some (bad!) solutions can be found on various websites. I want to proof a nice explicit form here (see below).↵
↵
It's trivial to solve this using (greedy) simulation (*). But Skiena and Revilla provide a short hint:↵
↵
_Can the constraints be usefully modeled using a DAG?_↵
↵
I thought about constructing a DAG where longest path corresponds to optimal solution. Unfortunately, my best approach is to use $(a_1, a_2, \dots, a_N)$ as state where $a_i$ denotes number on ball on top of peg $i$; exponential number of vertices is bad. How to use this hint in a suitable way?↵
↵
Considering small cases, one find the answers↵
↵
_1, 3, 7, 11, 17, 23, 31, 39, 49, 59, ..._↵
↵
for 1, 2, 3, ... pegs respectively. I conjecture that $\left\lfloor \frac{(N + 1)^2}{2} \right\rfloor - 1$ is the answer in general.↵
↵
Crawling through roughly a dozen websites with trivial simulation and no comments, I encountered a [chinese article](http://blog.csdn.net/tigerisland45/article/details/73196532) where a recurrence relation is given but not proven: $h(1) = 1$, $h(2) = 3$, $h(i) = h(i - 1) + i$ for even $i$ and $h(i) = h(i - 1) + i + 1$ for odd $i$.↵
↵
Finally, there are two questions:↵
↵
- How to utilize a DAG suitable?↵
↵
- How to prove the recurrence and/or explicit form (if correct)?↵
↵
Any kind of help and interesting ideas are appreciated!↵
↵
↵
(*) It's not immediately clear that solution isunbounded and greedy simulation is correct.
↵
It's trivial to solve this using (greedy) simulation (*). But Skiena and Revilla provide a short hint:↵
↵
_Can the constraints be usefully modeled using a DAG?_↵
↵
I thought about constructing a DAG where longest path corresponds to optimal solution. Unfortunately, my best approach is to use $(a_1, a_2, \dots, a_N)$ as state where $a_i$ denotes number on ball on top of peg $i$; exponential number of vertices is bad. How to use this hint in a suitable way?↵
↵
Considering small cases, one find the answers↵
↵
_1, 3, 7, 11, 17, 23, 31, 39, 49, 59, ..._↵
↵
for 1, 2, 3, ... pegs respectively. I conjecture that $\left\lfloor \frac{(N + 1)^2}{2} \right\rfloor - 1$ is the answer in general.↵
↵
Crawling through roughly a dozen websites with trivial simulation and no comments, I encountered a [chinese article](http://blog.csdn.net/tigerisland45/article/details/73196532) where a recurrence relation is given but not proven: $h(1) = 1$, $h(2) = 3$, $h(i) = h(i - 1) + i$ for even $i$ and $h(i) = h(i - 1) + i + 1$ for odd $i$.↵
↵
Finally, there are two questions:↵
↵
- How to utilize a DAG suitable?↵
↵
- How to prove the recurrence and/or explicit form (if correct)?↵
↵
Any kind of help and interesting ideas are appreciated!↵
↵
↵
(*) It's not immediately clear that solution is
