Betrachten Sie das folgende Kartenspiel (in Italien als "Cavacamicia" bekannt, was mit "stripshirt" übersetzt werden kann):

Zwei Spieler teilen zufällig ein Standardkartenstapel in zwei Stapel. Jeder Spieler erhält ein Deck.

Die Spieler legen abwechselnd die nächste Karte von ihrem Stapel ab.

Wenn ein Spieler (A) eine spezielle Karte ablegt, dh eine I-, II- oder III-Karte, muss der andere Spieler (B) nacheinander die entsprechende Anzahl von Karten ablegen.

• Wenn dabei B eine spezielle Karte ablegt, kehrt sich die Aktion um und so weiter. andernfalls sammelt A alle abgelegten Karten und fügt sie ihrem Stapel hinzu, wenn B die entsprechende Anzahl von Karten, aber keine spezielle Karte ablegt. Dann startet A das Spiel neu, indem eine Karte abgelegt wird.

Der erste Spieler, dem die Karten ausgehen, verliert das Spiel.

Hinweis: Das Ergebnis des Spiels hängt ausschließlich von der anfänglichen Partition des Decks ab. (Womit dieses Spiel vielleicht ein bisschen sinnlos aussieht ;-)

Frage: Beendet dieses Spiel immer? Was ist, wenn wir dieses Spiel verallgemeinern und jedem Spieler zwei beliebige Kartenfolgen geben?

In Bezug auf Bettler-Mein-Nachbar

Paulhus (1, S.164) schrieb 1999:

Wenn ein volles Kartenspiel ist, ist D $C$einen Zyklus haben? Wir lassen diese Frage unbeantwortet, mit der Ausnahme, dass wir keine von 3,2 Milliarden zufällig ausgewählten Deals finden konnten.${D_{2}}^{'}(C)$

Aber Conway et al. (2, S.892) schrieb im Jahr 2006:

Strip-Jack-Naked oder Bettler-Mein-Nachbar ** 1

Ein weiteres Problem, dessen Lösung fast 47 Jahre in Anspruch nahm, betrifft dieses alte Kinderspiel. Jeder der beiden Spieler beginnt mit etwa der Hälfte der Karten (verdeckt gehalten), die er abwechselnd auf einen offenen „Stapel“ auf dem Tisch legt, bis einer von ihnen (der jetzt „der Kommandant“ ist) das erste Mal austeilt eine der "Befehlskarten" (Bube, Dame, König oder Ass).

Nachdem einer dieser Karten ausgeteilt wurde, deckt der andere Spieler (jetzt „der Antwortende“) die Karten fortlaufend auf, bis ENTWEDER. ** 2 eine neue Befehlskarte erscheint (wenn die Spieler die Rolle wechseln ** 3) oder 1, 2, 3 oder 4 Karten ohne Befehl wurden aufgedeckt. Im letzteren Fall dreht der Kommandant den Stapel um und legt ihn auf den Boden seiner Hand. Der Antwortende beginnt dann mit der Bildung eines neuen Stapels, indem er seine nächste Karte umdreht, und das Spiel wird wie zuvor fortgesetzt.

Ein Spieler, der alle Karten erwirbt, ist der Gewinner und in echten Spielen scheint es, dass immer jemand gewinnt. Die interessante mathematische Frage, die vor vielen Jahren von einem von uns gestellt wurde, lautete: „ Stimmt es wirklich, dass das Spiel immer endet?“ Marc Paulhus hat kürzlich die Antwort mit „Nein!“ Gefunden. Ungefähr 1 von 150.000 Spielen (mit den üblichen 52 Karten gespielt) geht für immer weiter.

Wir sind ziemlich zuversichtlich, dass niemand das Spiel so oft gespielt hat, daher muss die Chance (mit zufälligem Mischen), ein nicht beendendes Spiel in einem lebenslangen Spiel zu erleben, in der Tat sehr gering sein.

Genauso sicher ist es jedoch, dass die Gesamtanzahl der Spiele, die von den 4 Kindern der Welt gespielt wurden, deutlich über 150.000 liegen muss. Viele von ihnen waren theoretisch nicht terminierend. Wir stellen uns jedoch vor, dass in der Praxis die meisten von ihnen tatsächlich gekündigt haben, weil jemand einen Fehler gemacht hat.

Leider konnte ich in (2) keinen Hinweis auf die Entdeckung von Paulhus finden ... Ich würde gerne eine Abfolge von Karten sehen, die ein nicht terminierendes Spiel ergibt, um zu sagen, dass das Problem gelöst ist.

Im Jahr 2013 schrieben Lakshtanov und Aleksenko (3):

Für Kartenspiele vom Typ Beggar-My-Neighbor beweisen wir die Endlichkeit der mathematischen Erwartung der Spieldauer unter der Bedingung, dass ein Spieler, der die erste Karte spielt, zufällig ausgewählt wird und dass die Karten in einem Stapel gemischt werden, bevor sie auf den Tisch gelegt werden Deck. Das Ergebnis gilt auch für allgemeine Änderungen der Spielregeln. Mit anderen Worten, wir zeigen, dass der Graph der Markov-Kette für das Beggar-My-Neighbor-Spiel absorbiert wird. dh von jedem Scheitelpunkt gibt es mindestens einen Pfad, der zum Ende des Spiels führt.

aber ihre Regeln sind nicht die, die ich befolgt habe, als ich ein Kind war ;-)

Nach meinem besten Wissen wurde das längste Beggar-my-Neighbor-Spiel 2014 von William Rucklidge mit 7960 Karten gefunden :

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

In Bezug auf Cavacamicia

Normalerweise habe ich es mit einem 40-Karten-Deck gespielt, Simulationen mit einem halben Deck (nur 20 Karten) ergeben 16 Spiele ohne Abschluss bei insgesamt 3.448.400 Spielen.

Literaturverzeichnis

(1) PAULHUS, Marc M. Bettler, mein Nachbar. American Mathematical Monthly , 1999, 162 & ndash; 165. http://www.jstor.org/stable/2589054

(2) BERLEKAMP, Elwyn R .; CONWAY, John H .; GUY, Richard K. Wege für Ihre mathematischen Spiele, Band 4. AMC, 2003, 10: 12. http://www.maa.org/publications/maa-reviews/winning-ways-for-your-mathematical-plays -Volumen-4

(3) LAKSHTANOV, Evgenii Leonidovich; ALEKSENKO, Alena Il'inichna. Endlichkeit im Kartenspiel Beggar-My-Neighbor. Probleme der Informationsübertragung , 2013, 49.2: 163-166. http://dx.doi.org/10.1134/S0032946013020051