Rozważ następującą grę karcianą (znaną we Włoszech jako „Cavacamicia”, którą można przetłumaczyć jako „stripshirt”):

Dwóch graczy losowo dzieli na dwie talie standardową talię kart. Każdy gracz otrzymuje jedną talię.

Gracze naprzemiennie umieszczają na stosie następną kartę ze swojej talii.

Jeśli gracz (A) odkłada kartę specjalną, tj. I, II lub III, drugi gracz (B) musi odłożyć kolejno odpowiednią liczbę kart.

• Jeśli w ten sposób B umieszcza specjalną kartę, akcja się odwraca i tak dalej; w przeciwnym razie, jeśli B odłoży odpowiednią liczbę kart, ale nie ma karty specjalnej, A zbiera wszystkie karty, które zostały odłożone, i dodaje je do swojej talii. Następnie ponownie uruchamia grę, odkładając kartę.

Pierwszy gracz, któremu zabraknie kart, przegrywa.

Uwaga: Wynik gry zależy wyłącznie od początkowej partycji talii. (Co może sprawić, że ta gra będzie trochę bezcelowa ;-)

Pytanie: Czy ta gra zawsze się kończy? Co jeśli uogólnimy tę grę i damy każdemu graczowi dwie sekwencje kart?

Odnośnie Żebrak-Mój-Sąsiad

Paulhus (1, s.164) napisał w 1999 r .:

Jeśli to pełna talia kart, czy ma cykl? Pozostawiamy to pytanie bez odpowiedzi, z wyjątkiem stwierdzenia, że ​​nie byliśmy w stanie znaleźć jednej z 3,2 miliarda losowo wybranych transakcji.$C$${D_{2}}^{'}(C)$

Ale Conway i in. (2, str. 892) napisali w 2006 roku:

Strip-Jack-Naked lub Beggar-My-Neighbor ** 1

Kolejny problem, którego rozwiązanie zajęło prawie 47 lat, dotyczy tej gry dla starych dzieci. Każdy z dwóch graczy zaczyna od około połowy kart (trzymanych zakrytych), które na przemian zamieniają na „stos” odkrytych do góry na stole, aż jeden z nich (który jest teraz „dowódcą”) pierwszy rozdaje jedna z „kart dowodzenia” (walet, królowa, król lub as).

Po rozdaniu jednego z nich drugi gracz (obecnie „osoba odpowiadająca”) obraca karty w sposób ciągły, dopóki NIE JEST. ** 2 pojawia się nowa karta dowódcy (gdy gracze zmieniają role ** 3) lub odpowiednio 1, 2, 3 lub 4 karty niep dowódcze zostały obrócone. W tym drugim przypadku dowódca przewraca stos i łączy go z dnem ręki. Następnie osoba odpowiadająca rozpoczyna tworzenie nowego stosu, odwracając swoją kolejną kartę, i gra jest kontynuowana jak poprzednio.

Gracz, który zdobędzie wszystkie karty, jest zwycięzcą, aw prawdziwych grach wydaje się, że ktoś zawsze wygrywa. Interesujące matematyczne pytanie postawione przez jednego z nas wiele lat temu brzmiało: „czy to naprawdę prawda, że ​​gra zawsze się kończy?” Marc Paulhus znalazł ostatnio odpowiedź „nie!”. Około 1 na 150 000 gier (granych zwykłymi 52 kartami) trwa wiecznie.

Jesteśmy dość pewni, że nikt nie grał w tę grę tyle razy, więc szansa (z losowym tasowaniem) na doświadczenie nie kończącej się gry w ciągu całego życia musi być naprawdę bardzo mała.

Jednak z całą pewnością łączna liczba przypadków, w które grała w tę grę ** 4 dzieci na świecie, musi być znacznie większa niż 150 000, więc wiele z nich teoretycznie nie kończy nauki. Wyobrażamy sobie jednak, że w praktyce większość z nich faktycznie zakończyła działalność, ponieważ ktoś popełnił błąd.

Niestety nie udało mi się znaleźć w (2) żadnej wzmianki o odkryciu Paulhus ... Chciałbym zobaczyć sekwencję kart, która daje grę nie kończącą się, aby powiedzieć, że problem został rozwiązany.

W 2013 roku Lakshtanov i Aleksenko (3) napisali:

W przypadku gier karcianych typu Beggar-My-Neighbor udowadniamy skończoność matematycznych oczekiwań dotyczących czasu gry, pod warunkiem, że gracz, który zagra pierwszą kartę, jest losowo wybierany, a karty ze stosu są tasowane przed umieszczeniem na pokład. Wynik obowiązuje również dla ogólnych modyfikacji zasad gry. Innymi słowy, pokazujemy, że wykres łańcucha Markowa dla gry Beggar-My-Neighbor jest absorbujący; tzn. z dowolnego wierzchołka jest co najmniej jedna ścieżka prowadząca do końca gry.

ale ich zasady nie są tymi, których przestrzegałem, gdy grałem w nią jako dziecko ;-)

O ile mi wiadomo, najdłuższa gra Beggar-my-Neighbor została znaleziona w 2014 roku przez Williama Rucklidge z 7960 kartami :

1: -J------Q------AAA-----QQ-
2: K----JA-----------KQ-K-JJK

W odniesieniu do Cavacamicia

Zwykle grałem w nią z talią 40 kart, symulacje z pół talią (tylko 20 kart) dają 16 niekończących się gier w sumie 3.448.400 gier.

Bibliografia

(1) PAULHUS, Marc M. Żebrak, mój sąsiad. American Mathematical Monthly , 1999, 162-165. http://www.jstor.org/stable/2589054

(2) BERLEKAMP, Elwyn R .; CONWAY, John H .; GUY, Richard K. Winning Ways For Your Mathematical Plays, Tom 4. AMC, 2003, 10: 12. http://www.maa.org/publications/maa-reviews/winning-ways-for-your-mathematical-plays -objętość-4

(3) LAKSHTANOV, Evgenii Leonidovich; ALEKSENKO, Alena Il'inichna. Skończoność w grze karcianej Żebrak-Mój-Sąsiad. Problemy z przesyłaniem informacji , 2013, 49.2: 163-166. http://dx.doi.org/10.1134/S0032946013020051