Bulgarian solitaire

In mathematics and game theory, Bulgarian solitaire is a card game that was introduced by Martin Gardner.[1]

Rules

In the game, a pack of ${\displaystyle N}$ cards is divided into several piles. Then for each pile, remove one card; collect the removed cards together to form a new pile (piles of zero size are ignored).

If ${\displaystyle N}$ is a triangular number (that is, ${\displaystyle N=1+2+\cdots +k}$ for some ${\displaystyle k}$), then it is known that Bulgarian solitaire will reach a stable configuration in which the sizes of the piles are ${\displaystyle 1,2,\ldots ,k}$. This state is reached in ${\displaystyle k^{2}-k}$ moves or fewer. If ${\displaystyle N}$ is not triangular, no stable configuration exists and a limit cycle is reached.

Random Bulgarian solitaire

In random Bulgarian solitaire or stochastic Bulgarian solitaire a pack of ${\displaystyle N}$ cards is divided into several piles. Then for each pile, either leave it intact or, with a fixed probability ${\displaystyle p}$, remove one card; collect the removed cards together to form a new pile (piles of zero size are ignored). This is a finite irreducible Markov chain.

History

Martin Gardner introduced the game in the August 1983 issue of Scientific American.[1]

In 2004, Brazilian probabilist Serguei Popov demonstrated that stochastic Bulgarian solitaire spends "most" of its time in a "roughly" triangular distribution.[2]

See also

• List of Martin Gardner Mathematical Games columns

References

1. Akin, Ethan; Davis, Morton (April 1985). "Bulgarian Solitaire". The American Mathematical Monthly. 92 (4): 237–250. doi:10.2307/2323643. JSTOR 2323643.
2. Popov, Serguei (October 2005). "Random Bulgarian solitaire". Random Structures and Algorithms. 27 (3): 310–330. arXiv:math/0401385. doi:10.1002/rsa.20076. ISSN 1042-9832.