Bulgarian solitaire
Encyclopedia
In mathematics
and game theory
, Bulgarian solitaire is a random card
game.
In the game, a pack of
cards is divided into several piles. Then for each pile, either leave it intact or, with a fixed probability
, remove one card; collect the removed cards together to form a new pile (piles of zero size are ignored).
If
, the game is known as Bulgarian solitaire or deterministic Bulgarian solitaire and was introduced by Martin Gardner
; the general case with
is known as random Bulgarian solitaire or stochastic Bulgarian solitaire. This is a finite irreducible Markov chain
.
If
is a triangular number
(that is,
for some 
), then it is known that deterministic Bulgarian solitaire will reach a stable configuration in which the sizes of the piles are 
. This state is reached in 
moves or fewer. If 
is not triangular, no stable configuration exists and a limit cycle is reached.
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.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
and game theory
Game theory
Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...
, Bulgarian solitaire is a random card
Playing card
A playing card is a piece of specially prepared heavy paper, thin cardboard, plastic-coated paper, cotton-paper blend, or thin plastic, marked with distinguishing motifs and used as one of a set for playing card games...
game.
In the game, a pack of
cards is divided into several piles. Then for each pile, either leave it intact or, with a fixed probabilityProbability
Probability is ordinarily used to describe an attitude of mind towards some proposition of whose truth we arenot certain. The proposition of interest is usually of the form "Will a specific event occur?" The attitude of mind is of the form "How certain are we that the event will occur?" The...
, remove one card; collect the removed cards together to form a new pile (piles of zero size are ignored).If
, the game is known as Bulgarian solitaire or deterministic Bulgarian solitaire and was introduced by Martin GardnerMartin Gardner
Martin Gardner was an American mathematics and science writer specializing in recreational mathematics, but with interests encompassing micromagic, stage magic, literature , philosophy, scientific skepticism, and religion...
; the general case with
is known as random Bulgarian solitaire or stochastic Bulgarian solitaire. This is a finite irreducible Markov chainMarkov chain
A Markov chain, named after Andrey Markov, is a mathematical system that undergoes transitions from one state to another, between a finite or countable number of possible states. It is a random process characterized as memoryless: the next state depends only on the current state and not on the...
.
If
is a triangular numberTriangular number
A triangular number or triangle number numbers the objects that can form an equilateral triangle, as in the diagram on the right. The nth triangle number is the number of dots in a triangle with n dots on a side; it is the sum of the n natural numbers from 1 to n...
(that is,
for some ), then it is known that deterministic Bulgarian solitaire will reach a stable configuration in which the sizes of the piles are . This state is reached in moves or fewer. If is not triangular, no stable configuration exists and a limit cycle is reached.In 2004, Brazil
Brazil
Brazil , officially the Federative Republic of Brazil , is the largest country in South America. It is the world's fifth largest country, both by geographical area and by population with over 192 million people...
ian probabilist
Probability
Probability is ordinarily used to describe an attitude of mind towards some proposition of whose truth we arenot certain. The proposition of interest is usually of the form "Will a specific event occur?" The attitude of mind is of the form "How certain are we that the event will occur?" The...
of Russia
Russia
Russia or , officially known as both Russia and the Russian Federation , is a country in northern Eurasia. It is a federal semi-presidential republic, comprising 83 federal subjects...
n origin Serguei Popov showed that stochastic Bulgarian solitaire spends "most" of its time in a "roughly" triangular distribution.