Mancala World
Don't have an account?
Register
Register
in: Modern Mancala Games, Stacking Games, Solitaires, No Rows

Changes: Bulgarian Solitaire

Back to page
View source
 
(5 intermediate revisions by the same user not shown)
Line 2: Line 2:
 
|'''Bulgarian Solitaire'''
  
|'''Bulgarian Solitaire'''
 
|-
  
|-
−
|''Other Names:'' Deterministic <br /> Bulgarian Solitaire, Karatsuba<br /> Solitaire
 +
|''Other Names:'' Deterministic <br /> Bulgarian Solitaire, Bulgarisk <br /> Patiens, Karatsuba Solitaire
 
|-
  
|-
−
|''Inventor:'' (?), 1981
+
|''Inventor:'' (?), 1980
 
|-
  
|-
 
|''Ranks:'' n/a
  
|''Ranks:'' n/a
Line 13: Line 13:
 
|}
  
|}
   
−
'''Bulgarian Solitaire''', also known as '''Deterministic Bulgarian Solitaire''', was first described in the Russian magazine "Kvant" in 1981, which already gave a solution to the problem. The famous American recreational mathematician [[Martin Gardner]] made it popular in 1983, when he wrote about the game in the renowned magazine "Scientific American".
 +
'''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 created, such as [[Austrian Solitaire]] (Ethan Akin & Morton David Davis (USA), 1985), [[Montreal Solitaire]] (Chris Cannings & John Haigh (England), 1992), [[Random Bulgarian Solitaire]] (Serguei Popov (Brazil), 2003) and [[Two-handed Bulgarian Solitaire]] (Tim Bancroft (USA), 2004). Gardner's game is based on a traditional Bulgarian game that is known as [[Carolina Solitaire]]. His game and its variants are extensively researched in Combinatorial Game Theory (CGT). It employs reverse sowing.
 +
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]]"''.
  
Prof. Su Dorée of Augsburg College, Minneapolis, USA, called Bulgarian Solitaire ''"a somewhat distant relative of the two-player African pebble games [[Mancala]]"''.
Line 21: Line 21:
 
==Rules==
  
==Rules==
   
−
The game is played by just one person.
 +
The game is played by one person.
   
−
In the game, a group of N cards is divided into several decks (or "piles").
 +
A group of N cards is divided into several decks (or "piles").
   
−
Then one card is removed from each deck.
 +
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 removed cards are collected together to form a new deck (piles of zero size are ignored).
Line 45: Line 45:
 
;Bending, T.: ''Bulgarian Solitaire''. In: ''Eureka'' 1990; 50 (April): 12-19.
  
;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.
  
;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.: [http://www.rpi.edu/~eglash/isgem.dir/texts.dir/OwariII.pdf Owari II. Marching Groups and Bulgarian Solitaire]. 2007.
  
;Bouchet, A.: [http://www.rpi.edu/~eglash/isgem.dir/texts.dir/OwariII.pdf 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.
 
;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.
 
;Etienne, G.: ''Tableaux de Young et Solitaire Bulgare''. In: ''Journal of Combinatorial Theory Series A'' 1991; 58: 181-197.
Line 54: Line 56:
 
;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.
  
;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.: ''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.: [http://mymath-files.com/MAA/CollegeMathJournal/March2012.pdf 30 Years of Bulgarian Solitaire]. In: ''The College Mathematics Journal'' 135-140.
 +
;Hopkins, B.: [http://mymath-files.com/MAA/CollegeMathJournal/March2012.pdf 30 Years of Bulgarian Solitaire]. In: ''The College Mathematics Journal'' 2012; 43 (2) 135-140.
 
;Hopkins, B. & Jones, M. A. : [http://www.emis.ams.org/journals/EJC/Volume_13/PDF/v13i1r80.pdf Shift-Induced Dynamical Systems on Partitions and Compositions]. In: ''Electronic Journal of Combinatorics'' 2006; 13 #R80.
  
;Hopkins, B. & Jones, M. A. : [http://www.emis.ams.org/journals/EJC/Volume_13/PDF/v13i1r80.pdf Shift-Induced Dynamical Systems on Partitions and Compositions]. In: ''Electronic Journal of Combinatorics'' 2006; 13 #R80.
 
;Hopkins, B. & Sellers, J. A.: [http://www.emis.de/journals/INTEGERS/papers/a19int2005/a19int2005.pdf Exact Numeration of Garden of Eden Partitions]. In: ''Integers: Electronic Journal of Combinatorial Number Theory'' 2007; 7 (2), #A19.
  
;Hopkins, B. & Sellers, J. A.: [http://www.emis.de/journals/INTEGERS/papers/a19int2005/a19int2005.pdf Exact Numeration of Garden of Eden Partitions]. In: ''Integers: Electronic Journal of Combinatorial Number Theory'' 2007; 7 (2), #A19.
Line 60: Line 62:
 
;Meštrović, R.: ''An Inductive Proof of a Result about Bulgarian Solitaire''. In: ''Ars Combinatoria'' 2010; 95 (4): 6.
  
;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.
  
;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==
  
==External Links==

Latest revision as of 13:28, 11 October 2012

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

Copyright

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

Community content is available under CC-BY-SA unless otherwise noted.