Bulgarian Solitaire

In this article we provide investigate a famous classical process involving piles of stones (or originally cards) introduced by Martin Gardner.

The game involves a set of piles of stones with $\frac{n(n+1)}{2}$ stones in total. In each move, the topmost stone in each pile is picked and a new pile is formed with these stones. The goal is to show that eventually we end up with $n$ piles of stones with $1,2,\dots , n$ stones in them respectively.

Despite the overwhelming amount of work on this topic, it was almost impossible to find a clear and intuitive solution which appreciates the beauty of this process. The following solution is due to Tony Wang.

1. Setting up an attack

In order to attack the problem, we first need to come up with some representation or setup which allows us to record the variation in the distribution of piles.

The most natural way to do this is to represent each stone as a dot, and let dots be in the same column if they are in the same pile. Now, we have a choice to make on how we represent the movement of stones. For example, we can always place the new pile in the rightmost position.

In each case, the highlighted stones are those which are picked to form a new pile.

However, one realizes it is extremely difficult to understand how the piles that using this representation, partly since the piles which ‘disappear’ leave empty columns. Always rearranging the piles so that they are in decreasing order of size is even more obscure since the position of each new pile is already hard to control.

To fix this issue we utilize the following process to go from one position to the next.

Algorithm : Let $\ell$ denote the line parallel to the line $y=x$ which passes through the lattice point to the immediate left of the leftmost point in the bottom row. Reflect the bottom row across $\ell$ and move the entire system by a vector of $(1,-1)$ .

It is clear that this corresponds to the given operation since the bottom-most stone in each column ends up in the leftmost new column. However, one might notice that this leads to situations when there are columns with spaces in between stones. Since this is awkward, we imagine the stones to be in a world where gravity exists and the stones fall down. So, a stone will occupy the lowest position available in it’s column.

Repeating the previous example using this algorithm,

Using this representation, we show the stronger claim that not only will the piles eventually be of sizes $1,2,\dots , n$ but they will lie precisely within the region bounded by the lines $x=0$ , $y=0$ and $y=-x+n$ .

2. ‘Inventing’ information to track

Increasing the amount of information available for tracking is an incredibly powerful tool since it allows us to treat the system more ‘rigidly’. In this case, allowing the stones to be indistinguishable leaves a lot of ambiguity about which stone goes where, so to increase the rigidity of the system we treat each stone independently.

The trick is now to look at the trajectories of each individual stone, and the reason why the above representation is so powerful is simply because it allows us to achieve this goal beautifully.

For example, the stone at $(0,0)$ always stays there since the reflection sends it to $(-1,1)$ and the displacement vector sends it back to where it started. In fact, this is precisely the way to motivate this representation – it ‘anchors the base point’, so to speak.

To make things more clear, we shall repeat the previous example, this time highlighting each distinct stone in a different color.

Let a diagonal be a line parallel to the line $y=-x$ . Looking at the above picture, we can make two key observations.

Each stone cycles within the diagonal it lies in, so its ‘diagonal number’ is non-increasing.
Furthermore, if a stone lands in a position which has no stone underneath it, by gravity it falls down to a smaller diagonal.

We shall now work out the finer details of these two heuristics.

3. Fine tuning and Proofs

If a stone is not at the bottom row, it simply moves by the vector $(-1,1)$ and hence stays within the same diagonal (assuming it does not fall down). If a stone is at the bottom row, then it moves from $(x,0)$ to $(-1,x+1)$ which are in the same diagonal (once again assuming it does not fall down).

Now, in order to finish, we simply need to show that it is impossible for some stone to never fall down if it has to.

Consider the smallest isosceles right triangle with a vertex at $(0,0)$ which is completely filled. Say there exists some lattice point in diagonal $d$ which is not occupied (called a hole, say $h$ ), and at least one stone outside the filled triangle and diagonal $d$ .

Clearly at least one of these stones (say $s$ ) lies on diagonal $d+1$ (since stones must fall down if they are able to). We claim that this stone eventually fills the unoccupied point in diagonal $d$ . As noted before, each stone of diagonal $d$ cycles within the diagonal, moving one position during each move, and hence has period $d$ . If the stones cycle with period $d$ and the holes remain unfilled, then the holes also cycle with the same period. Similarly, the stone $s$ in diagonal $d+1$ cycles with period $d+1$ .

However, since $\gcd(d,d+1)=1$ eventually (within $d(d+1)$ moves) the hole $h$ and stone $s$ must line up, at which point $s$ occupies the position of the hole, which contradicts our assumption that $h$ remains a hole.

Hence, any holes must be filled in a finite number of steps and indeed we are left with the perfect triangle configuration, as desired.