An Inductive Proof of a Result About Bulgarian Solitaire

Abstract

Let $N$ be a positive integer and let $\lambda =({\lambda }_1,{\lambda }_2,\dots ,{\lambda }_l)$ be a partition of $N$ of length $l$, i.e., $\sum _{i=1}^l{\lambda }_i=N$ with parts ${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_l\ge 1$. Define $T(\lambda )$ as the partition of $N$ with parts $l$, ${\lambda }_1–1,{\lambda }_2–1,\dots ,{\lambda }_l–1$, ignoring any zeros that might occur. Starting with a partition $\lambda$ of $N$, we describe Bulgarian Solitaire by repeatedly applying the shift operation $T$ to obtain the sequence of partitions

$$\lambda ,T(\lambda ),T^2(\lambda ),\dots$$

We say a partition $\mathcal{A}$ of $N$ is $T$-cyclic if $T^i(\mu )=\mu$ for some $i\ge 1$. Brandt $[2]$ characterized all $T$-cyclic partitions for Bulgarian Solitaire. In this paper, we give an inductive proof of Brandt’s result.