Bulgara ermitludo
En matematiko kaj ludoteorio, bulgara ermitludo estas hazarda kartludo.
En la ludo, pako de N kartoj estas dividita en kelkajn amasojn. Tiam por ĉiu amaso, ludanto (la sola) kun fiksita probablo p forprenas unu karton aŭ alie (kun probablo 1-p) ne tuŝas la amason; la forprenitaj kartoj estas kolektataj kune kaj formas la novan amason; amasoj de nula amplekso estas ignoritaj.
Se p=1, la ludo estas sciata kiel bulgara ermitludo aŭ determinisma bulgara ermitludo kaj estis prezentita per Martin Gardner; la ĝenerala okazo kun 0<p<1 estas sciata kiel hazarda bulgara ermitludo aŭ stokasta bulgara ermitludo. Ĉi tiu estas finia nereduktebla markova ĉeno.
Se N estas triangula nombro (tio estas, N=1+2+ ..+k por iu k), do estas sciate ke determinisma bulgara ermitludo atingas stabilan konfiguron en kiu la ampleksoj de amasoj estas 1, 2, ..., k. Ĉi tiu stato estas atingata en ne pli ol k2-k movoj. Se N ne estas triangula nombro, stabila konfiguro ne ekzistas kaj limiga ciklo estas atingata.
En 2004, Serguei Popov montris ke stokasta Bulgara ermitludo pasigas plejparton de evolua tempo en la malglate triangula distribuo.
Referencoj
[redakti | redakti fonton]- Serguei Popov (2005). “Random Bulgarian solitaire - Hazarda bulgara ermitludo”, Random Structures and Algorithms - Hazardaj Strukturoj kaj Algoritmoj 27(3), p. 310–330. doi:10.1002/rsa.20076.
- Ethan Akin kaj Morton Davis (1985). “Bulgarian solitaire - Bulgara ermitludo”, American Mathematical Monthly 92(4), p. 237–250.