Bulgarian solitaire

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

Rules

In the game, a pack of $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 $N$ is a triangular number (that is, $N=1+2+\cdots +k$ for some $k$), then it is known that Bulgarian solitaire will reach a stable configuration in which the sizes of the piles are $1,2,\ldots ,k$. This state is reached in $k^{2}-k$ moves or fewer. If $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 $N$ cards is divided into several piles. Then for each pile, either leave it intact or, with a fixed probability $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.

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

See also

• List of Martin Gardner Mathematical Games columns