Math Problem: Hanoi Tower Troubles Again!
Difference between en1 and en2, changed 2 character(s)
[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 is 
unbounded and greedy simulation is correct.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English neutron-byte 2018-01-16 23:51:44 2 Tiny change: 'lution is unbounded an' -> 'lution is bounded an'
en1 English neutron-byte 2018-01-16 23:45:43 1720 Initial revision (published)