Bulgarian solitaire
In mathematics and game theory, Bulgarian solitaire is a card game that was introduced by Martin Gardner.
In the game, a pack of [math]\displaystyle{ N }[/math] 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 [math]\displaystyle{ N }[/math] is a triangular number (that is, [math]\displaystyle{ N=1+2+\cdots+k }[/math] for some [math]\displaystyle{ k }[/math]), then it is known that Bulgarian solitaire will reach a stable configuration in which the sizes of the piles are [math]\displaystyle{ 1,2,\ldots, k }[/math]. This state is reached in [math]\displaystyle{ k^2-k }[/math] moves or fewer. If [math]\displaystyle{ N }[/math] 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 [math]\displaystyle{ N }[/math] cards is divided into several piles. Then for each pile, either leave it intact or, with a fixed probability [math]\displaystyle{ p }[/math], 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.
In 2004, Brazil ian probabilist of Russia n origin Serguei Popov showed that stochastic Bulgarian solitaire spends "most" of its time in a "roughly" triangular distribution.
References
- Serguei Popov (2005). "Random Bulgarian solitaire". Random Structures and Algorithms 27 (3): 310–330. doi:10.1002/rsa.20076.
- Ethan Akin and Morton Davis (1985). "Bulgarian solitaire". American Mathematical Monthly 92 (4): 237–250. doi:10.2307/2323643.
Original source: https://en.wikipedia.org/wiki/Bulgarian solitaire.
Read more |