What's the most efficient way to put all the stones in one pile?

There are $k$ piles of $n_i$ stones, on every move you can choose two piles with sizes $a$ and $b$ and if $a \ge b$ take from the first pile $b$ stones and put to the second one, on other hand if $a < b$ - take $a$ from the second and put them to the first. What is the necessary and sufficient condition to put all stones in one pile and what is the smallest number of such operations to do it?

The first question is rather simple: iff $\frac{\sum{n_i}}{\gcd(n_1, n_2 ... n_k)}=2^p$ But I dont know answer for the second one, I can prove that it is $O(kp)$, but I think that we can do it much more quicker and my hypothesis is $O(k + p))$. Can anyone to prove it or may be refuse it?

May be there exists some better estimation for the number of moves, if you have, please tell me.

Solution 1:

It seems the following.

Fix $p$ and $k$. Without loss of generality, we can assume that $\gcd(n_1, n_2 ... n_k)=1$.

At first we calculate the number $P(p,k)$ of different possible initial positions $(n_1, n_2 ... n_k)$. It is well known and easy to show that the number $S(K,k)$ of different sequences $(n_1, n_2 ... n_k)$ of nonnegative integers (not necessarily satisfying the condition $\gcd(n_1, n_2 ... n_k)=1$) with $\sum n_i=K$ is equal to ${K+k-1}\choose{k-1}$. Fortunately, in our case $K=2^p$ is a power of a prime number $2$. Therefore we have that $\gcd(n_1, n_2 ... n_k)\not=1$ iff all $n_i$ are even. Thus the number $P(p,k)$ of different sequences $(n_1, n_2 ... n_k)$ satisfying the condition $\gcd(n_1, n_2 ... n_k)=1$ with $\sum n_i=K$ is equal to $S(K,k)–S(K/2,k)$.

Now we have the tree of positions with initial $P(p,k)$ vertices and $k$ roots and on each move we are going down to the root. It is easy to check that if a position $B$ was obtained from a position $A$ by moving stones from $i$-th pile to $j$-th, then the position $A$ is uniquely determined by $B$, $i$ and $j$. Therefore each vertex of the tree has no more than $k(k-1)$ vertices above it. Thus if we can reach a root of the tree from each of its vertices after going down at most $m$ moves, we should have the inequality $k[k(k-1)]^{m-1}\ge P=(p,k)$. In particular, for large $k$ and $2^p>>k$ it should give an asymptotic lower bound on $m$ of order $\frac{pk}{\operatorname{log}_2 k}-k$.