Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let we have $n\cdot(n+1)/2$ stones grouped by piles. We can pick up 1 stone from each pile and put them as a new pile. Show that after doing it some times we will get the following piles: $1, 2, \ldots n$ stones.

Example: $n = 3$

Let we have 2 piles with 3 stones of each.

$$3 3 \to 2 2 2 \to 1 1 1 3 \to 2 4 \to 1 3 2$$

share|improve this question
4  
This is the "Bulgarian solitaire" problem; it is related to sequence A201144 in OEIS. –  MJD Dec 8 '12 at 18:17
2  

2 Answers 2

up vote 5 down vote accepted

This was originally proved by Jørgen Brandt in Cycles of Partitions, Proceedings of the American Mathematical Society, Vol. 85, No. 3 (Jul., 1982), pp. 483-486, which is freely available here. The proof of this result covers the first page and a half and is pretty terse.

First note that there are only finitely many possible sets of pile sizes, so at some point a position must repeat a previous position. Say that $P_{m+p}=P_m$ for some $p>0$, where $P_n$ is the $n$-th position (set of pile sizes) in the game. It’s not hard to see that the game will then cycle through the positions $P_{m+k}$, $k=0,\dots,p-1$, repeatedly. The proof consists in showing that when there are $\frac12n(n+1)$ pebbles, the only possible cycle is the one of length one from $\{1,2,\dots,n\}$ to $\{1,2,\dots,n\}$.

Brian Hopkins, 30 Years of Bulgarian Solitaire, The College Mathematics Journal, Vol. 43, No. 2, March 2012, pp. 135-140, has references to other published proofs; one appears to be to a less accessible version of the paper Karatsuba Solitaire (Therese A. Hart, Gabriel Khan, Mizan R. Khan) that MJD found at arXiv.org.

Added: And having now read the Hart, Khan, & Khan paper, I agree with MJD: the argument is quite simple, and it’s presented very well.

share|improve this answer
    
A few months ago I read a paper which had a really simple proof, and I have been trying since then to find it again. Early in the paper it alluded to a simple inductive proof, which the authors had been told about but not seen, and which they (and I) tried in vain to find. –  MJD Dec 9 '12 at 3:07
    
Aha, it's Karatsuba Solitaire by Hart, Khan, and Khan. "Karatsuba said the solution to this problem was an interesting exercise in mathematical induction. We have been unable to discover such a proof…" –  MJD Dec 9 '12 at 3:11
1  
Hopkins's paper has an entertaining exposition of the history of the problem. For example: "Meanwhile, Eriksson traveled from Stockholm to California, where he called the puzzle Bulgarian solitaire. He recently explained, “The silly name is my invention, silly because it is neither Bulgarian nor a solitaire.” [...] The silly name has stuck." –  Andres Caicedo Dec 9 '12 at 4:00

The following is an attempt to succinctly summarise the solution in the Hart, Kahn, and Kahn paper that MJD indicated, so I claim no originality for the solution. I will however use a somewhat different terminology.

To elucidate the dynamics of the "Bulgarian solitaire" transformation, a "potential energy" statistic is defined on configurations, which the transformation never increases. For this we order both the piles (by weakly decreasing size after each transformation) and the stones of each pile (from bottom to top), numbering the piles and stones starting from $0$. The potential energy of each stone is then the sum of the numbers of its pile and of its position in the pile, and the total potential energy is the sum of those of all the stones. One can visualise this by placing the piles on a staircase, the first (tallest) pile at level $0$, the next at level $1$ and so forth.

The transformation consists of two steps: the first "shaving off" the bottom stones of each pile to form a new pile numbered $0$ (the stones keeping their energy), while increasing the number of what is left of the piles; the second sorting the piles into weakly decreasing order, which just means "bubbling" pile number $0$ to a higher number as long as it is smaller than its successor. It is easy to see that the first step does not change the potential energy, while the second step can only decrease it, and will indeed decrease it whenever there is actual permuting of piles.

When the transformation is iterated and an ultimate cycle is reached, then the potential energy must be constant during that cycle, so the second part of the transformation never permutes anything anymore. Then every stone retains its potential energy $e$, and cyles periodically through the $e+1$ piles numbered $0,1,\ldots,e$. For any level $e\in\mathbf N$, the $e+1$ positions of potential energy $e$ can be all filled (a full level), all empty (an empty level), or some can be fulled and other empty (a partially filled level). Clearly if a level is full then previous levels are also full, and it a level is empty then successive levels are also empty. The final point to show is that in the ultimate cycle there can be no two consecutive partially filled levels.

Supposing for a contradiction that levels $e$ and $e+1$ are both partially filled, then in each of these levels there is a filled position with the position just behind it empty. Since the periods $e+1$ and $e+2$ are relatively prime, we can iterate until both these filled positions are in pile $0$, and after one more transformation those two positions in pile $0$ will be empty. But then at that point pile $0$ has become shorter than pile $1$, contradicting the fact that no permutation of piles is necessary in the ultimate cycle. So there is at most one partially filled level: the full levels give the largest trianglar number not exceeding the number of stones, and any remaining stones fill a subset of the following level. If the number of stones is a triangular number, then there are no remaining stones.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.