Bulgarian Solitaire: Size of root loops

I first learned of Bulgarian solitaire from one of Martin Gardner's books a while ago and have since investigated it somewhat. Google-searching has revealed that surprisingly little work has been done (publicly anyway) in this area.

The way the game works is as follows: take any number of items (like coins or small stones) and partition them into any number of piles with any number of items in each pile. Then take one item from each pile and make a new pile with them. Repeat for as long as necessary. For example:

$10$ items, starting with piles of $4, 4, 1, 1$

At first, there are four piles. Taking one item from each leaves us with $3, 3$. Adding back the four we took gives us $4, 3, 3$. Repeating this step results in...

$4, 4, 1, 1$
$4, 3, 3$
$3, 3, 2, 2$
$4, 2, 2, 1, 1$
$5, 3, 1, 1$
$4, 4, 2$
$3, 3, 3, 1$
$4, 2, 2, 2$
$4, 3, 1, 1, 1$
$5, 3, 2$
$4, 3, 2, 1$
$\mathbf{4, 3, 2, 1}$
$\dots$

Those with a good eye will quickly see that $4, 3, 2, 1$ is a stable state in that going through a turn of the game doesn't change anything. What is more interesting is that EVERY initial configuration of $10$ items will end up at this stable state. Additionally, $6$ items will always end up in $3, 2, 1$; $15$ items will always end up in $5, 4, 3, 2, 1$; and so on. Triangular numbers of items are the only numbers for which this happens. This is because only a $n, n-1, n-2, \dots, 3, 2, 1 { }$ state is stable; subtracting one from each gets rid of the $1$-pile and adds a pile of $n$. Clearly, a triangular number of items results in a "root loop" of size 1.

I'm going to go ahead and state an observation and a fact that follows from it. This observation is that all partitions of $n$ items will lead to exactly one other partition of $n$, by definition. This means that while loops can exist, there can never be a partition of $n$ that leads to two partitions of $n$. This has the effect of splitting a directed graph (an edge from $i$ to $j$ has weight 1 iff partition $i$ leads to partition $j$) into a number of subgraphs that exactly corresponds to the number of loops. This is not hard to prove, and I am not Fermat. :P

What I found to be even more interesting was what happened when you used a non-triangular number of items. In these cases, you will go into a loop. For example...

$7$
$6, 1$
$5, 2$
$4, 2, 1$
$3, 3, 1$
$3, 2, 2$
$3, 2, 1, 1$
$\mathbf{4, 2, 1}$
$\dots$

Thus, starting with $7$ items ends up in a root loop of size $4$. More experimenting reveals that given a non-triangular number $n$ of items, find the triangular number $T_k \geq n$ and $k$ is the size of at least one of the root loops in the directed graph of all partitions of $n$.

Why is this so?

This is probably covered in one of the papers that show up in Gerry's search, but since I spent a little time on it I will post a solution anyway. The solution is also relatively short.

El'endia's conjecture is correct. A cycle of the prescribed length can be constructed as follows. We first recall the fixed point partition $p_k=(k,k-1,k-2,\ldots,2,1)$ of the triangle number $n=T_k=k(k+1)/2$. Suppose that instead the total number of stones is $n=k(k+1)/2-m$, where $0<m<k$. I claim that in this case we get a cycle of length $k$ by removing one stone from the $m$ smallest piles of the partition $p_k$. In other words, let us study the partition $$p_k^*=(k,k-1,k-2,\ldots,m+1,m^*,(m-1)^*,...,2^*,1^*),$$ where I use the funny notation $\ell^*$ to denote a pile of $\ell-1$ stones, because that pile really wants to have $\ell$ stones, but it feels a little bit left out. Therefore $1^*$ really is an empty pile.

Let $p_k^{*,m,i}$ denote the partition gotten from $p_k$ by marking $m$ consecutive entries starting from the $i$-pile with an asterisk. If $i<m$, then we move the remaining asterisks to the beginning of the partition in the usual cyclic fashion (so the above partition $p_k^{*}=p_k^{*,m,m}$). For example, $$p_5^{*,3,2}=(5^*,4,3,2^*,1^*)=(4,4,3,1,0)=(4,4,3,1).$$ The key observation is that the Bulgarian solitaire move maps the partition $p_k^{*,m,i}$ to the partition $p_k^{*,m,i-1}$, where we interpret $i-1=0$ as $k$ (or decrement $i$ by one modulo $k$). This is easy to see, because the entries of all these partitions are in descending order. The only slightly tricky thing is that the empty pile $1^*$ corresponds to $k^*$ after the Bulgarian solitaire move, because the presence of an empty pile means that the new pile loses one of its stones, and gets only $k^*$ stones instead of the usual $k$.

As an example, let $n=25=28-3=T_7-3$. Then we get a cycle of 7 partitions starting with $(7,6,5,4,3^*,2^*,1^*)=(7,6,5,4,2,1)$. The cycle consists of the partitions $$(7^*,6,5,4,3,2^*,1^*)=(6,6,5,4,3,1),$$ $$(7^*,6^*,5,4,3,2,1^*)=(6,5,5,4,3,2),$$ $$(7^*,6^*,5^*,4,3,2,1)=(6,5,4,4,3,2,1),$$ $$(7,6^*,5^*,4^*,3,2,1)=(7,5,4,3,3,2,1),$$ $$(7,6,5^*,4^*,3^*,2,1)=(7,6,4,3,2,2,1),$$ $$(7,6,5,4^*,3^*,2^*,1)=(7,6,5,3,2,1,1),$$ and back to $$(7,6,5,4,3^*,2^*,1^*)=(7,6,5,4,2,1).$$

Several years ago, we wrote a paper which explains the dynamics of Bulgarian solitaire with a non-triangular number of the stones. It turns out that you can have root loops of various different sizes, but their lengths depends on the smallest triangular number $T_k$ with $T_k \geq n$. In particular, the length of all the loops will always divide $k$ and there will always be at least one of length $k$ (unless $n=T_k$). For a more complete exposition, you can find our paper here.