Hanoi Tower Troubles Again 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}, ..., *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 is the answer in general.

Crawling through roughly a dozen websites with trivial simulation and no comments, I encountered a chinese article 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 bounded and greedy simulation is correct.

Auto comment: topic has been updated by neutron-byte (previous revision, new revision, compare).Why couldn't we place infinity numbers of ball on one peg? I didn't see any constraints about maximum number write on a ball, or did i miss something?

Assume infinite number of balls is possible. If there are

Npegs, consider placing ball with number 2N^{2}on some peg. The smallest number which can be placed next on this peg is 2N^{2}+ 4N+ 1. Thus, we have to do the next 4Nmoves on the remainingN- 1 pegs. Similarly, we pair 2N^{2}+ 1 with 2N^{2}+ 4N, 2N^{2}+ 2 with 2N^{2}+ 4N- 1, ... , 2N^{2}+N- 1 with 2N^{2}+ 3N+ 1. Now, allNpegs are blocked, because all next possible numbers are greater than 2N^{2}+N. Thus, we established an upper bound of 2N^{2}+N- 1.Do a binary search for the answer

k. This way the problem can be reduced to the question "Cankballs 1, ...,kbe placed onnpegs?".The reduced question can be solved as a flow problem on a DAG. There is a vertex

afor every balla. There is an edgea→biffbcan be placed ona. (i.e.a<banda+bis a square.) Every vertex has capacity 1 (As every ball gets placed once.). Each vertex is connected to the source and the sink. The balls can be placed iff there is a flow of value at mostnthat saturates every edge corresponding to a vertex capacity. (The balls placed on a single peg correspond to a path in the flow decomposition of the flow. There are no cycles in the decomposition as the graph is acyclic.)On way to solve the DAG model is min-cost flow. The edges corresponding to vertex capacities have cost - 1, all other edges have cost

k. The covering flow exists iff there is a min cost flow of flow valuef≤nand of cost -n. This min-cost flow can be found in , so the total runtime is .The DAG model can also be solved by bipartite matching. There are two vertices

a,a' for every balla. There is an edgea→b' iffbcan be placed ona. The balls can be placed iff there is a matching of size at leastk-n. (The matching edges correspond to the saturated edges in the min-cost flow problem.) The total runtime is .Your formula for

h(k) is know on OEIS. It can probably be proven by induction on "h(k) = ... and there is an optimal solution such that the balls that are on top of the pegs have got the highestnnumbers.