Bulgarian Solitaire

Take a deck of cards and split them into piles of any sizes you like. Now apply one rule, over and over: take exactly one card from every existing pile, collect those cards into a brand-new pile, and repeat. That is Bulgarian Solitaire.

The rule looks harmless. But something astonishing happens when the total number of cards is a triangular number — a number of the form $T_k = 1 + 2 + \dots + k = \frac{k(k+1)}{2}$ for some positive integer $k$. No matter how you start, the piles will eventually reach the configuration $\{1, 2, 3, \dots, k\}$ — a perfect staircase — and stay there forever.

The game was popularized in the early 1980s, notably by the mathematician Martin Gardner in his Scientific American column (1983), and the convergence theorem was proved around the same time by Ethan Akin and Morton Davis (1985) and, independently, by several others. It is a rare example of a completely solved discrete dynamical system: no chaos, no cycles — just inevitable order.

Set the starting piles below — each number is the size of one pile. The total must be a triangular number ($T_k = k(k+1)/2$ for some $k$). Press Step to apply one round of the rule, or Run to animate until the staircase appears.

<!-- {{c_html_intro}} -->
<div class="controls">
  <label for="preset-select">{{label_preset}}</label>
  <select id="preset-select">
    <option value="6,4,1">6, 4, 1 (T₅ = 15)</option>
    <option value="4,3,2,1">4, 3, 2, 1 (T₄ = 10)</option>
    <option value="14,1">14, 1 (T₅ = 15)</option>
    <option value="custom">{{option_custom}}</option>
  </select>
  <input id="custom-input" type="text" placeholder="{{placeholder_custom}}" style="display:none" />
</div>
<div id="piles-display" class="piles-display" aria-label="{{aria_piles}}"></div>
<div id="status-bar" class="status-bar"></div>
<div class="btns">
  <button id="btn-step" type="button">{{btn_step}}</button>
  <button id="btn-run" type="button">{{btn_run}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div id="step-count" class="step-count"></div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 4px; }
.controls { display: flex; gap: .5rem; flex-wrap: wrap; align-items: center; margin-bottom: .6rem; font-size: .88rem; }
label { font-weight: 600; }
select, input[type=text] { font: .88rem system-ui, sans-serif; padding: .3rem .5rem;
  border: 1px solid #adb1b8; border-radius: 6px; background: #f5f7fa; }
.piles-display { display: flex; align-items: flex-end; gap: 6px; min-height: 140px;
  border-bottom: 2px solid #c0c8d2; padding-bottom: 4px; margin-bottom: .5rem;
  flex-wrap: wrap; }
.pile { display: flex; flex-direction: column; align-items: center; gap: 2px; }
.card { width: 28px; height: 18px; border-radius: 3px; background: #4a90d9; border: 1px solid #2f6db5; }
.card.new-pile { background: #e63946; border-color: #c92f3c; }
.pile-label { font-size: .7rem; font-weight: 700; color: #555; margin-top: 2px; }
.status-bar { font-size: .92rem; font-weight: 600; min-height: 1.4em; margin: .3rem 0; }
.status-bar.done { color: #0a7d33; }
.status-bar.running { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
  background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: not-allowed; }
.step-count { font-size: .82rem; color: #666; margin-top: .4rem; }
.target-note { font-size: .78rem; color: #888; margin-top: .3rem; }

// Code not found

Notice that the pile sizes jump around erratically at first, then gradually sort themselves out. The distance to the fixed point — measured as the sum of absolute differences from the target staircase — never increases on average, and must eventually reach zero. That monotonic decrease is the engine of the proof.

The proof that Bulgarian Solitaire always reaches the staircase is elegant and elementary.

The fixed point. When the total is $T_k = k(k+1)/2$, the only configuration the rule maps to itself is the staircase $\{1, 2, 3, \dots, k\}$. Applying the rule to the staircase takes one card from each of $k$ piles to form a pile of size $k$, and each remaining pile shrinks by one — giving $\{0, 1, 2, \dots, k-1\} \cup \{k\} = \{1, 2, \dots, k\}$ again (dropping the empty pile of size 0). The staircase is self-reproducing.

The monovariant. Define a score for any configuration as $\Phi = \sum_{i} p_i^2$ (the sum of squares of pile sizes). One can show that $\Phi$ either decreases or stays the same after each step, and it can only stay the same when the configuration is already the staircase. Since $\Phi$ is a non-negative integer, it must eventually stop decreasing — and that stopping point is the fixed point.

The bound. Starting from any configuration with $T_k$ cards, the staircase is always reached in at most $k(k-1)$ steps. For $k = 5$ that is at most 20 steps; for $k = 10$, at most 90. The convergence is fast and guaranteed.

Non-triangular totals behave differently: instead of a single fixed point the system falls into a cycle of configurations that keep repeating. The triangular-number condition is not an accident — it is precisely what ensures a fixed point exists.

This makes Bulgarian Solitaire a textbook example of a completely solved dynamical system: unlike the Collatz conjecture, there is no mystery about what happens in the long run.

Bulgarian Solitaire is small, but the ideas it showcases appear throughout mathematics and computer science:

• Monovariants and termination proofs: the same technique — find a quantity that always decreases toward a bound — is how we prove that algorithms terminate. Loop invariants in dynamic programming, decreasing potential functions in network protocols, and well-founded orderings in theorem provers all work the same way.
• Discrete dynamical systems: Bulgarian Solitaire is a simple model of a system that self-organizes. Similar convergence phenomena appear in cellular automata, sorting networks, and chip-firing games on graphs.
• Combinatorics and partition theory: the piles are integer partitions of $T_k$. The study of how partition operations behave is a central topic in combinatorics, with connections to Young tableaux, representation theory, and symmetric functions.
• Teaching fixed-point arguments: because the rule is so concrete, Bulgarian Solitaire is a favorite example for introducing students to fixed-point theorems — the idea that repeated application of a rule must eventually stop at a self-reproducing state.

Simple rules with inevitable outcomes: that is a pattern worth recognizing wherever you find it.

Bulgarian Solitaire is an almost absurdly simple process — take one card from each pile, make a new pile — yet it hides a theorem that feels like magic: from any starting arrangement, provided the total is a triangular number, the piles will march inexorably toward the perfect staircase $\{1, 2, \dots, k\}$ and never leave.

The key is the monovariant: a quantity that the rule is obliged to decrease, step after step, until there is nowhere left to go but the fixed point. That same logic — find what must decrease, conclude that it must stop — underlies termination proofs across all of algorithm design.

So the next time you wonder why a loop has to end, or why an iterative process has to converge, think of the card piles patiently sorting themselves into a staircase. Order does not always emerge from chaos — but when a monovariant is watching, it has no other choice.