Bulgarian Solitaire

Bulgarian Solitaire

Other Names: Deterministic Bulgarian Solitaire, Bulgarisk Patiens, Karatsuba Solitaire

Inventor: (?), 1980

Ranks: n/a

Sowing: Reverse

Region: Russia

Bulgarian Solitaire, also known as Deterministic Bulgarian Solitaire, was first described in the Russian magazine "Kvant" in 1980. An unknown man had shown the game to the Russian mathematician Konstantin Oskolkov, while he was travelling to Leningrad (now Saint Petersburg) to give a talk. The first solutions to the problem were found in 1981. The modern name of the puzzle ("Bulgarian Solitaire") was created by Henrik Eriksson of KTH Royal Institute of Technology in 1982. The famous American recreational mathematician Martin Gardner made it popular in 1983, when he wrote about the game in the renowned magazine "Scientific American".

Many variants were invented in later years, such as Austrian Solitaire (Ethan Akin & Morton David Davis (USA), 1985), Montreal Solitaire (Chris Cannings & John Haigh (England), 1992), Carolina Solitaire (Andrej Andreev (Bulgaria), 1997), Random Bulgarian Solitaire (Serguei Popov (Brazil), 2003) and Two-handed Bulgarian Solitaire (Tim Bancroft (USA), 2004). Bulgarian Solitaire and its variants are extensively researched in Combinatorial Game Theory (CGT).

Prof. Su Dorée of Augsburg College, Minneapolis, USA, called Bulgarian Solitaire "a somewhat distant relative of the two-player African pebble games Mancala".

Rules

The game is played by one person.

A group of N cards is divided into several decks (or "piles").

After that one card is removed from each deck.

The removed cards are collected together to form a new deck (piles of zero size are ignored).

The decks are not ordered, so it doesn't matter in which order the cards are being removed or where the new pile is placed.

The game ends when the same position occurs again.

Variant

If N is a triangular number, the game is also called Karatsuba Solitaire. It was invented by the Russian mathematician Anatolii A. Karatsuba who first mentioned it during a visit in Bulgaria sometime in the 1990s.

Mathematics

If N is a triangular number (that is, N = 1 + 2 + ... +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, ... k. This state is reached k² − k moves or fewer. If N is not triangular, no stable configuration exists and a limit cycle is reached.

References

Akin, E. & Davis, M.

Bulgarian Solitaire. In: American Mathematical Monthly 1984 (2); 92: 237-250.

Bending, T.

Bulgarian Solitaire. In: Eureka 1990; 50 (April): 12-19.

Bentz, H.-J.

Proof of the Bulgarian Solitaire Conjectures. In: Ars Combinatoria 1987; 23: 151-170.

Bojanov, B.

Problem Solution 4. In: Obuchenieto po matematica 1981; 24 (5): 59-60.

Bouchet, A.

Owari II. Marching Groups and Bulgarian Solitaire. 2007.

Brandt, J.

Cycles of Partitions. In: Proceedings of the American Mathematical Society 1982; 85: 483-486.

Eriksson, A.

Bulgarisk Patiens. In: Elementa 1981; 64 (4): 186-188.

Etienne, G.

Tableaux de Young et Solitaire Bulgare. In: Journal of Combinatorial Theory Series A 1991; 58: 181-197.

Gardner, M.

Mathematical Games. (a.k.a Bulgarian Solitaire and Other Seemingly Endless Tasks). In: Scientific American 1983; 249: 8-13 or 12-21.

Griggs, J. R. & Ho, C.-C.

The Cycling of Partitions and Compositions under Repeated Shifts. In: Advances in Applied Mathematics 1998; 21: 205-227.

Gwihen, E.

Tableaux de Young et Solitaire Bulgare. In: Journal of Combinatorial Theory 1991 (2); 58: 181-197.

Hart, T. H., Khan, G. & Khan, Mizan, R.

Karatsuba Solitaire (eprint arXiv:1101.1546). Cornell University Library, Ithaca NY (USA) 2011.

Hobby, J. D. & Knuth, D.

Problem 1: Bulgarian Solitaire. In: A Programming and Problem-Solving Seminar. Department of Computer Science, Stanford University, Stanford (USA) 1983 (December): 6-13.

Hopkins, B.

Column-to-Row Operations on Partitions: The Envelopes. In: Landman, B., Nathanson, M. B., Nešetril, J., Nowakowski, R. J., Pomerance, C., Robertson, A. (Eds.). Combinatorial Number Theory: Proceedings of the 'Integers Conference 2007'. Carrollton, Georgia, October 24—27, 2007. Walter de Gruyter, Berlin (Germany) & New York (USA) 2009, 65–76.

Hopkins, B.

30 Years of Bulgarian Solitaire. In: The College Mathematics Journal 2012; 43 (2) 135-140.

Hopkins, B. & Jones, M. A.

Shift-Induced Dynamical Systems on Partitions and Compositions. In: Electronic Journal of Combinatorics 2006; 13 #R80.

Hopkins, B. & Sellers, J. A.

Exact Numeration of Garden of Eden Partitions. In: Integers: Electronic Journal of Combinatorial Number Theory 2007; 7 (2), #A19.

Igusa, K.

Proof of the Bulgarian Solitaire Conjecture. In: Mathematics Magazine 1985 (5); 58: 259-271.

Meštrović, R.

An Inductive Proof of a Result about Bulgarian Solitaire. In: Ars Combinatoria 2010; 95 (4): 6.

Nicholson, A.

Bulgarian Solitaire. In: Mathematics Teacher 1993; 86: 84-86.

Toom, A.

Problem Solution M655. In: Kvant 1981; 12 (7): 28-30.

External Links

• Martin Gardner

Copyright

© Wikimanqala.
By: Ralf Gering
Under the CC by-sa 2.5 license.