lvi. Bulgarian Solitaire

Problem (Gardner, 1983). Split $n$ cards into piles. A move takes one card from every pile and forms a new pile from them. If $n=1+2+\cdots +k$ is triangular, show that from any start the piles become $1,2,\dots ,k$ (and then stay there).

Fact	Value
fixed point for $n=k(k+1)/2$	the staircase $(k,k-1,\dots ,1)$; it is reached from every start
moves needed, triangular $n$	at most $k^2-k$ (Igusa 1985, Etienne 1991), and this is attained for $k\ge 2$
$n=k(k+1)/2+r$, $1\le r\le k$	ends in a cycle: the staircase plus $r$ extra cards on “diagonal $k$”, rotating; cycle length divides $k+1$
method	Young diagram, diagonals, and a potential (energy) that never increases

vector<int> bulgarianStep(vector<int> p) {           // piles in non-increasing order
    int k = sz(p);
    for (auto& x : p) x--;
    p.push_back(k);
    p.erase(remove(all(p), 0), p.end());
    sort(all(p), greater<int>());
    return p;
}
 
int stepsToFixedPoint(vector<int> p) {               // number of moves until the position repeats itself
    sort(all(p), greater<int>()); int s = 0;
    for (auto q = bulgarianStep(p); q != p; p = q, q = bulgarianStep(q)) s++;
    return s;
}

Proof: convergence to the staircase

Draw the piles as rows of a Young diagram, largest first: cell $(i,j)$ exists iff $j<p_i$. Call $i+j$ the diagonal of a cell; diagonal $d$ has $d+1$ positions. Let the energy be $E={\sum }_{\text{cells}}(i+j)$.

A move is a rotation followed by sorting. Removing one card from each pile deletes column 0; the new pile has $c=$ (number of piles) cards. Put it as row 0 and shift the old rows down by one: cell $(i,j)$ with $j\ge 1$ goes to $(i+1,j-1)$ and cell $(i,0)$ goes to $(0,i)$. Every cell stays on its diagonal; on diagonal $d$ the cell in row $r$ moves to row $r+1$, and the one in row $d$ (column 0) wraps to row 0: a cyclic shift of the $d+1$ positions. If the resulting rows are not in non-increasing order (the new row is shorter than the next), sorting moves the new row down by adjacent swaps; each swap of a shorter row above a longer one moves the longer row’s extra cells up one row, onto the diagonal below. So $E$ never increases, and strictly decreases whenever sorting changes anything.

Eventually only rotations. $E$ is a non-negative integer, so after finitely many moves no more sorting happens and the position just rotates every diagonal. Suppose then that some diagonal $d$ has an empty position while diagonal $d+1$ has a cell. Their rotations have periods $d+1$ and $d+2$, which are coprime, so by the Chinese remainder theorem at some time the hole sits at $(0,d)$ and the cell at $(0,d+1)$, i.e. row 0 has a cell right of a gap. That is not a valid diagram, so sorting would occur, a contradiction. Hence in the final regime, a diagonal with a hole is followed only by empty diagonals: the cells fill diagonals $0,1,\dots$ completely, except possibly the last non-empty one.

Conclusion. For $n=k(k+1)/2=1+2+\cdots +k$ that means diagonals $\mathrm{0..}k-1$ are full and nothing else: the staircase, which maps to itself. For $n=k(k+1)/2+r$ with $1\le r\le k$, diagonals $\mathrm{0..}k-1$ are full and $r$ cells sit on diagonal $k$, rotating with period dividing $k+1$. The bound $k^2-k$ is the cited theorem; the search checked it, and that it is attained, for every partition with $k\le 10$ ($n\le 55$), together with the cycle shape for every $n\le 50$.

Related notes

• Invariants, Parity and Extremal Arguments (potential arguments)
• Stirling, Bell and Partitions (Young diagrams)
• Cycles and Functional Graphs (every deterministic process ends in a cycle)