Bulgarian solitaire

In mathematics and game theory, Bulgarian solitaire is a random card game.

In the game, a pack of $N$ cards are 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).

If $p=1$, the game is known as "Bulgarian solitaire" or "deterministic Bulgarian solitaire" and was introduced by Martin Gardner; the general case with

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

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

References

*cite journal | author= Serguei Popov| title= Random Bulgarian solitaire| journal= Random Structures and Algorithms| year=2005| volume=27(3) | pages=310–330| unused_data= |DOI 10.1002/rsa.20076
*