Revisiting Toom’s proof of Bulgarian Solitaire

As an undergraduate, my parents and I wrote an expository paper on Bulgarian solitaire. It was the first paper I ever wrote and one of my fondest memories about how satisfying it is to crack a stubborn problem. When we first heard about it, we had no idea that it was a well-known problem that Russian high-schoolers were expected to solve, but more on that later. The problem was published in the high school journal Kvant in 1980 in the following form (translated from Russian).

On the table of a clerk at the Circumlocution Office there are n volumes of Encyclopedia Britannica, ordered in several piles. Every day, upon arriving to work, the clerk takes one volume from each pile and puts all of these in a new pile, after which he rearranges the piles according to the number of volumes in each (in non-increasing order), and fills out a form, recording the number of volumes in each pile. He never does anything else, except this.

1. What record will he enter in the form after a month, if the total number of volumes is n = 3, n = 6, n = 10 (the initial distributions of volumes is arbitrary)?
2. Prove that if the total number of volumes is n = k(k + 1)/2, where k is a natural number, then after a certain amount of days the form will start filling up with identical records.
3. Investigate what will happen after many working days for other values of n.

Andrei Toom

If you haven’t heard of this problem before, I encourage you to spend a bit of time working on it. It’s very simple to state but surprisingly tough to solve unless you know the trick to it. If you just want the answer, here is a link to the paper.

Hart et al. (web)Download

Our attempts at Bulgarian Solitaire

My dad first learned about this problem from one of his colleagues at work. At the time, we did not know anything about its history and only that Anatoly Karatsuba had apparently mentioned that it was an “interesting exercise in mathematical induction.” In fact, neither my dad nor several of his colleagues were able to find this inductive proof. My mom then tested many different starting configurations of piles to understand the dynamics of the system. However, no one was able to find a proof.

One weekend I came home and my parents mentioned the problem to me. I was immediately hooked. I had just taken a course on dynamical systems and this system seemed so simple, but had proven to be quite stubborn. On the train back into Boston, I started sketching various different configurations and realized that the trick was to consider the diagonal, which would essentially be fixed under the dynamics of the system. Furthermore, there was a quantity (the maximum occupied diagonal) which would not increase under iterations of the process.

Over the next few days, I cobbled together an argument that certain configurations living above the diagonal could not recur, and thus the only possible fixed point was the simple triangular pattern. This gave an absurdly complicated proof, but one which was not particularly informative. Also, the write-up was abysmal. Writing clear mathematics has never been my strength, but I am much better now than as an undergraduate.

Fortunately for me, my parents were willing to slog through the (hand-written!) notes to figure out if the proof held water. My mom and I tried to get the argument into an understandable form. However, my dad figured that although the idea of the diagonal was essential, the rest of the proof could be radically simplified by an application of the Chinese Remainder Theorem. And thus we finally had a reasonably clear and simple proof.

Writing the result

Of course, my next experience was learning that writing a paper generally takes much longer than actually solving the problem. I naively expected this to be be a quick process, but I was wrong. As you can probably tell from the tone/quality of the writing, my dad wrote most of the exposition. But after several months of writing and editing, we finally had a preprint that all three of us were happy with. And so we posted our result to the Arxiv.

And the next day, we got several e-mails telling us that this was a well-known problem for high-schoolers. So a week later we withdrew the paper off the Arxiv.

But despite the embarrassment, we got a few friendly e-mails as well, including one from Claude Levesque saying they had enjoyed the paper and asking us to submit it to the Annales des sciences mathématiques du Québec. Somewhat sheepishly, we rewrote our work as an expository paper and Christian Yankov and Z. Pozdnyakova translated the original Russian references sources for us. After doing so, the editor was still willing to review the paper and after some minor revisions, it was finally published in 2012 in Ann. Sci. Math. Québec.

A lost paper

Normally, this would be the end of the story. Once you publish a paper, there’s generally not much else to do with it. However, in 2013 Annales des sciences mathématiques du Québec was acquired by Springer and became Annales mathématiques du Québec. This was no issue for nearly 10 years, as the paper was available on the old website. However, sometime in the past year or so, this old website was taken down and all the old papers were lost to history. While updating my CV, I realized that the link to the journal was dead and since we had never updated Arxiv, the paper was completely lost.

Fortunately, we were able to dig up a copy from the journal as well as the Latex code. We’ve since updated the Arxiv to have the current version, which should be a more permanent reference.

Lessons learned

I’m very fond of this paper, both for sentimental reasons as well as all the lessons it taught me.

1. Look for monotonic quantities!
   This was the key insight to Bulgarian solitaire, and searching for monotonic/conserved quantities is something that I’ve used many times since.
2. Spend a lot of time with your writing and try to make things as clear as possible!
   Had it used the original proof, the paper would have been borderline unreadable. And had we tried to post it before all the edits, it’s likely that no one would have reached out except to tell us that the problem was well-known and solved. The only reason that we were able to convert it to an expository work was the effort my parents put towards writing a clear and insightful paper.
3. Mathematical research is always a messy process, both with solving problems and getting them published!
   Long ago, I’ve lost count of how many false starts and setbacks I’ve had in mathematics as well as the number of rejections I’ve gotten while submitting my work. This paper provided a real learning experience in how convoluted the process from the initial problem to the final paper can be.
4. Keep back-ups of your old work and make them publicly available!
   Papers (and theorems themselves) are routinely forgotten and rediscovered. This process is inevitable and a natural consequence of how enormous the field of mathematics has become. However, there are certain things that you can do to extend the natural life of your work. If you make it publicly (and easily) available, this will help preserve your work.
5. Do a thorough literature review!
   We should have realized that Bulgarian solitaire was well-known and it definitely taught me a lesson about doing a more careful literature review. However, rediscovering known results is a constant aspect of math research, especially when the old versions are hard to find. It can be frustrating, but sometimes deriving things that were previously known is actually a sign of good progress.