k piles with $k(k+1)/2$ balls

Question

Given $\frac{k(k+1)}{2}$ balls arranged in $m$ piles.

A player picks a ball from each pile and creates a new pile.

As a result, piles with one ball disappear, and a new pile with $m$ balls is created.

For example ($k=2$), if we sort the piles by their size: $$(1,1,1)\rightarrow (3) \rightarrow (1,2) \rightarrow (1,2)$$

It is easy to see, that for any $k$: $$(1,2,\dots,k)\rightarrow (1,2,\dots,k)$$

Let $(1,2,\dots,k)$ be denoted as the stationary state

Show that no matter what is the initial configuration of piles, the piles configuration would converge to the stationary state.

Answer 1

Thanks to the comment by Michael Lugo, I found a paper covering the "Bulgarian solitaire" problem and the solution.

I knew the solution is based on setting a function that decreases in every move, however I was having problem coming up with the function.

The function the paper describes, is the potential energy (height times mass times g) of the balls, when the piles are vertical and placed in a box, in the case that the box is rotated to 45 degrees.

See full paper here

I've tested their solution in python and it works:

f = lambda x: sum([(len(x)-i)*t+(t+1)*t/2.0 for i,t in enumerate(x)])

Where x is sorted tuple that describes how many balls are in each pile.

you can see my full code here