Balancing balls in bins The following is a classic problem: There are $k$ bins with $n_1, \ldots, n_k$ balls such that $n_1+\dots+n_k = n$. If $n_i < n_j - 1$, we may move one ball from bin $j$ into bin $i$. By defining the potential function $n_1^2 + \dots + n_k^2$, it is easy to show that this process ends after at most $n^2$ moves.
Consider this variant: There are now positive constants $c_1,\ldots, c_k$ (which may not be integers). If $c_in_i < c_j(n_j-1)$, we may move one ball from bin $j$ into bin $i$. I can show that this process again terminates. But does it always terminate after at most $n^2$ (or even some polynomial in $n$) moves?
 A: The energy analogy works also for the extension with $c_i$'s, however bounding the number of moves does not work equally well. Below is first the standard problem, then the one wich $c_i$'s. A big part has already been alluded into the comments; one minor difference here is energy which is $\frac {n(n-1)} 2$ instead of $n^2$, because the analogy looks better. Then comes a tentative counterexample that unfortunately does not work (thanks @Alexi for your comment).
Each ball has a potential energy proportional to its height. On the classic problem, balls in bin $i$ have heights $0, 1, 2, ..., n_i-1$. The total potential of bin $i$ is therefore $n_i(n_i-1)/2$. So total energy of the system is $E = \frac 1 2 \sum_{i=1}^k n_i(n_i-1)$.
When a ball is transferred from bin $j$ to bin $i$, the top ball in bin $j$ goes to the top of bin $i$. The difference in energy is
$E - E' = \frac 1 2 (n_j(n_j-1) + n_i(n_i-1) - (n_j-1)(n_j-2) - (n_i+1)n_i)$
$= \frac 1 2 (n_j^2-n_j+n_i^2-n_i-n_j^2+3n_j-2-n_i^2-n_i)$
$= \frac 1 2 (2n_j-2n_i-2) = n_j-n_i-1$
Which is actually the difference in height of the transferred ball.
By hypothesis this quantity is always $> 0$, and hence, being an integer, $\ge 1$.
So on each movement the energy decreases by at least $1$.
The minimum energy is attained when the $n_i$'s are all within a distance $1$.
As $\sum_{i=1}^k n_i = n$, this energy is $\ge$ to the energy attained by an equirepartition of the $n_i$'s in all the bins, i.e. to
$E_{min} = \frac 1 2 \sum_{i=1}^k \frac n k (\frac n k - 1) = \frac n 2 (\frac n k - 1)$ (or $E_{min} = 0$ if $n < k$)
So the number of moves is bounded by $\frac 1 2 (\sum_{i=1}^k n_i(n_i-1) - n(\frac n k - 1))$
This bound is tight when all moves decrease the energy by $1$, e.g.
$(3, 1, 0, 0) \rightarrow (2, 2, 0, 0) \rightarrow (1, 2, 1, 0) \rightarrow (1, 1, 1, 1)$
The bound can be simplified into $\frac {n^2} 2$, because
$\sum_{i=1}^k n_i(n_i-1) < \sum_{i=1}^k n_i^2 \le (\sum_{i=1}^k n_i)^2 = n^2$
so $\frac 1 2 (\sum_{i=1}^k n_i(n_i-1) - n(\frac n k - 1)) < \frac 1 2 (n^2 - n(\frac n k - 1)) < \frac {n^2} 2$
Now on the problem with $c_i$'s. The $c_i$'s are actually invertly proportional to the bins horizontal surface, and the balls are apparently so soft (or liquid) that they fill whatever surface is available ;-). So the heights of balls in bin $i$ are now $0, c_i, 2c_i, ..., (n_i-1)c_i$. The total potential energy of bin $i$ is $\frac 1 2 c_i n_i(n_i-1)$. Total energy of the system is $E = \frac 1 2 \sum_{i=1}^k c_i n_i(n_i-1)$.
When a ball is transferred from bin $j$ to bin $i$, its height goes from $c_j(n_j-1)$ to $c_i n_i$. So, guess what,
$E-E' = \frac 1 2 (c_j n_j(n_j-1) + c_i n_i(n_i-1) - c_j(n_j-1)(n_j-2) - c_i(n_i+1)n_i)$
$= \frac 1 2 (c_j n_j^2-c_j n_j+c_i n_i^2-c_i n_i-c_j n_j^2+3c_j n_j-2c_j-c_i n_i^2-c_i n_i)$
$= \frac 1 2 (2 c_j n_j - 2 c_i n_i - 2 c_j) = c_j (n_j-1) - c_i n_i$
which is the height difference for the transferred ball.
By hypothesis, this quantity is $> 0$. However, on the contrary to the standard problem, we cannot say that this quantity is an integer, so we cannot give it a lower bound.
One could try transforming this problem back into an integer problem which has at least the same number of movements. As anything that matters are the relative positions of the $c_i n_i$ during the process, if $N = \sup_{i=1..k} n_i$, we would look for $d_i \in \mathbb{N}$, such that we can replace any $c_ip$ by $d_ip$, while retaining the inequalities. I.e. $\forall p \in \mathbb{N}, p \le N, \forall q \in \mathbb{N}, q \le N, c_i p < c_j q \Leftrightarrow d_i p < d_j q$. But that's not obvious, and moreover if the $c_i$ are irrationnal between themselves, the $d_i$ have to grow with $N$, which we want to avoid.
One difficulty is whether it is possible to get true cyclic behaviors: it is easy to build examples where a ball gets back to a bin where it previously were, but it seems very difficult to find one where this is repeated for at least a fixed fraction of the balls, i.e. finding a pattern that can be applied to any large $n$.
Edit 2 As @ThomasAhle remarked in a comment, with $n$ balls there are at most $n$ possible levels on each non-empty bin. As a ball can only make a movement downwards, it cannot be twice in the same level at the same bin; so each ball can then transit through at most $kn$ positions. As there are $n$ balls this makes a maximum of $kn^2$ movements.
It still looks like $n^2$ is a valid bound, but reasoning upon each energy transition is not sufficient, as stated above, because we do not have a lower bound on each individual transition. A better approach should take into account:

*

*A bound for the sum of all transitions. If the $c_i$ are irrational between them, we cannot bound the difference between two multiples of them, however this difference still cannot be low for all transitions, even if taking only into account, for each $n_j$, the optimal transitions, i.e. between $n_j$ and $n_i$ such that $c_i n_i$ is closer to (and below of) $c_j (n_j-1)$.

*A situation where an optimal transition is possible requires $n_i-1$ balls in bin $i$. This costs movements to install, and is destroyed after use; it seems not possible to chain those optimal transitions without a great number of non-optimal transitions.


The tentative counterexample was the following.
Let's have $k$ bins where $c_1 > c_2 > ... > c_k$. We begin with $n-k+1$ balls in bin $1$, and $1$ ball in each other bin. We then transfer each ball from bin $1$ one by one to the right, as long as we can transfer them. The first ball goes all the way to bin $k$. The second ball can go as far as bin $k-1$ (and can go to bin $k$ if $c_{k-1} > 2 c_k$, but we will not take into account this case, as we are only looking for a counterexample). The third ball to $k-2$, etc. So the first $k-1$ balls make $\frac {k(k-1)} 2$ movements. Then, as there are two balls on each bin from $2$ to $k$, we can repeat the process, as long as there are sufficient balls in bin $1$ and the top ball is sufficiently high. At least this can be done for $\lfloor \frac {n-k+1} 2 \rfloor$ balls.
So with these $n$ balls we make at least $\frac 1 {k-1} \lfloor \frac {n-k+1} 2 \rfloor \frac {k(k-1)} 2 = \lfloor \frac {n-k+1} 2 \rfloor \frac k 2$ movements. Edit Unfortunately, this is only valid if $k < n$, so $\lfloor \frac {n-k+1} 2 \rfloor \frac k 2$ is still $< n^2$, hence not a counterexample.
A: Michael's potential function
$$L(n_1, ..., n_k) = \sum_{i=1}^k c_i(n_i^2 - n_i)$$
indeed works, which means that any legal move decreases the potential function. Thus, we cannot return to the same state (problem is acyclic and will thus terminate).
I think it should not be too hard to show, that for any $n, k$ and any distribution of $c_i$ the worst-case scenario (highest potential, most possible moves) is attained when all balls start in the bin with highest value of $c$. For simplicity, we sort all bins with respect to $c$ in descending order and place all balls into the first bin.
Under the simplifying assumption that each ball is only allowed to visit each bin once, it is easy to show that the bound is $(n^2 -2n)/4$. It is attained by moving all except 2 balls in the next bin. Note that the initial rule forbids us from moving the last two balls as the value of the source bin would be zero and thus smaller than the target bin. To see that this number of moves can indeed happen in practice, it is enough to set each of the following $c_{i+1} \ll c_i \forall i$.
The problem is that the balls can visit the same bin more than once. It is my strong suspicion that it does not make the problem worse at all, but I don't know how to prove it yet.
Consider two bins with the same value $c$ where the first has $m+1$ balls in it and the second has $m$. We can perform sequence of moving three balls out of the first bin somewhere else, then moving the top ball of the second to the first, then moving three balls out of the second bin somewhere else, then moving the top ball of the first to the second and so on. Technically, there will be one ball that will make a large number of jumps between the two bins. However, there will be far less moves in total than in the worst-case scenario.
I'll attempt to come back to this when I have an idea how to finish this proof. I suspect that the bound holds, but I don't quite see the right invariant just yet
