Direkt zum Inhalt

Ordnung durch Mischen

Je sorgfältiger man Spielkarten ineinanderblättert, desto schlechter sind sie hinterher gemischt. Das kann so weit gehen, daß die ursprüngliche Reihenfolge wiederhergestellt wird.


Bei den meisten Kartenspielen ist der erste Schritt vor dem eigentlichen Spiel das Mischen. Damit sollen die Karten in eine möglichst zufällige Reihenfolge gebracht werden. Das Paradox dabei ist: Je perfekter die Mischung, desto unzufälliger das Ergebnis. Das gilt zumindest für die geläufige Mischtechnik, bei der man den Stapel in zwei Hälften teilt und beide Teilstapel sorgfältig ineinanderblättert (riffle shuffle, Bild). Der Gipfel der Geschicklichkeit ist es, die Karten stets genau eins links, eins rechts auf den gemeinsamen Stapel fallen zu lassen. Aber genau dann ist jede Zufälligkeit dahin.

Denken wir zunächst an einen Stapel aus zehn Karten, alle von derselben Farbe und der Reihe nach geordnet, das As oben und die Zehn unten. Heben Sie zwischen den Karten 5 und 6 ab und mischen Sie die beiden Hälften sorgfältig ineinander. Wenn die erste Karte der oberen Hälfte oberste Karte des gemischten Stapels wird, dann ist dessen Reihenfolge As, 6, 2, 7, 3, 8, 4, 9, 5, 10. Wenn statt dessen die erste Karte der unteren Hälfte zuoberst gerät, ergibt sich die Reihenfolge 6, As, 7, 2, 8, 3, 9, 4, 10, 5. Die erste Methode heißt out-shuffle ("Ausmischen"), die zweite in-shuffle ("Einmischen").

Die älteste bekannte schriftliche Quelle für diese Mischtechnik ist ein Buch eines unbekannten Autors aus dem Jahre 1726 mit dem Titel "Whole Art and Mystery of Modern Gaming". Ein gewisser J. H. Green brachte 1843 in "An Exposure of the Arts and Miseries of Gambling" diese kulturelle Errungenschaft nach Amerika. Der Rancher Fred Black aus Nebraska brachte es zu früher Meisterschaft im Kartenmischen zu Pferde und fand zahlreiche mathematische Ergebnisse für das wiederholte Ausmischen eines üblichen 52-Karten-Spiels. Der englische Zauberkünstler Alex Elmsley veröffentlichte 1957 zahlreiche mathematische Sätze für Kartenspiele jeder Größe.

Ausmischen ist im wesentlichen dasselbe wie Einmischen mit zwei Karten weniger: Man lege von unserem Zehnerstapel das As und die Zehn vorübergehend beiseite, vollführe ein Einmischen mit den Karten 2 bis 9 und bringe die Beiseitegelegten an ihre alten Plätze, dann ergibt sich die Reihenfolge As, 6, 2, 7, 3, 8, 4, 9, 5, 10 – wie beim Ausmischen aller zehn Karten. Es genügt daher, nur eines der beiden Mischverfahren zu betrachten.

Was geschieht nun, wenn wir mit unserem Zehnerspiel mehrfaches Einmischen veranstalten? Gerät die Reihenfolge der Karten immer mehr durcheinander? Das sieht zunächst so aus. Nach dreimaligem Mischen liegen die Karten in der Folge 7, 3, 10, 6, 2, 9, 5, As, 8, 4. Aber nach dem fünften Mischen hat sich die ursprüngliche Reihenfolge gerade umgekehrt! Fünf weitere Mischvorgänge kehren die Umkehrung nochmals um, und die Karten liegen wieder wie zu Anfang. Danach geschieht nichts Neues mehr. Wiederholtes Einmischen, angewandt auf zehn Karten, liefert also nur zehn verschiedene Reihenfolgen – ein winziger Bruchteil aller 10!=3628800 Möglichkeiten, zehn Karten anzuordnen.

Wenn Sie statt zehn irgendeine gerade Anzahl n von Karten mehrfach einmischen, werden Sie feststellen, daß stets die ursprüngliche Reihenfolge wieder erscheint, und zwar weit bevor die n! möglichen Reihenfolgen erschöpft sind. Warum? Ein Einmischvorgang tut das, was die Mathematiker eine Permutation nennen: Jede Karte wechselt auf den Platz einer anderen (oder bleibt auf ihrem Platz). Dabei kommt es nicht darauf an, welche Karte es ist, sondern nur, auf welchem Platz sie gerade liegt. Das Diagramm links zeigt den Weg jeder Karte für den Fall n=10. Das As wandert auf den Platz der Zwei, diese auf den Platz der Vier und so weiter. Jede Karte nimmt den Platz ihrer Nachfolgerin in der folgenden Kette ein: As -> 2 -> 4 -> 8 -> 5 -> 10 -> 9 -> 7 -> 3 -> 6 -> As. Da dieser Zyklus 10 Schritte enthält, muß nach zehnmaligem Mischen jede Karte wieder an ihrem Ursprungsplatz angekommen sein.

Diese und die folgenden Überlegungen gelten auch für ungerade Kartenanzahlen. Nur läßt sich dann der Stapel nicht mehr in zwei gleiche Teile zerlegen, und man muß vereinbaren, daß stets der obere (oder stets der untere) Teilstapel die überzählige Karte enthalten soll.

Daß es nur eine solche zyklische Permutation gibt, ist eher untypisch. Häufiger zerfällt die Permutation in mehrere Zyklen, so bei einem Spiel mit 8 Karten (unten im Diagramm) in die zwei Zyklen As -> 2 -> 4 -> 8 -> 7 -> 5 -> As und 3 -> 6 -> 3. Nach sechsmaligem Mischen sind die Karten aus dem ersten Zyklus wieder in der ursprünglichen Reihenfolge, die aus dem zweiten bereits nach zweimaligem Mischen. Wenn nach sechs Mischakten der erste Zyklus einmal rundgelaufen ist, hat der zweite schon drei Runden hinter sich.

Einerlei, wie viele Karten im Spiel sind, ihre Bewegung zerfällt stets in eine Anzahl solcher Zyklen. Warum? Fassen Sie eine Karte ins Auge und verfolgen Sie ihren Weg. Da es nur endlich viele Plätze gibt, muß die Karte irgendwann einen erreichen, auf dem sie schon einmal gelegen hat. Und der erste derartige Platz muß ihr ursprünglicher Platz sein. Warum? Weil der Mischvorgang im Prinzip eindeutig umkehrbar ist: Nehmen Sie den gemischten Stapel, geben Sie die Karten von unten nach oben eins rechts, eins links an zwei gedachte Spieler aus und legen Sie die beiden so entstandenen Stapel aufeinander. Die Umkehrung des Einmischens heißt in-sort ("Einsortieren"), die des Ausmischens out-sort ("Aussortieren").

Wenn also eine Karte nach dem achten Mischakt auf demselben Platz liegt wie nach dem dritten, dann muß sie nach dem siebten Mischakt bereits auf demselben Platz gelegen haben wie nach dem zweiten, und so weiter. Also muß der erste Platz, den eine Karte zum wiederholten Male einnimmt, ihr Anfangsplatz sein. Aus ähnlichen Gründen kann eine Karte nicht von einem Zyklus in einen anderen springen.

Sind die Zyklen erst einmal bekannt, kann man leicht ermitteln, nach wie vielen Mischakten die ursprüngliche Ordnung wiederhergestellt ist. In einem Zyklus der Länge k sind alle Karten nach k-maligem Mischen in ihrer Ausgangsposition. Bei mehr als einem Zyklus kommt es auf das kleinste gemeinsame Vielfache aller Zykluslängen an. Nehmen wir beispielsweise an, es gebe zwei Zyklen mit den Längen 10 und 14. Dann liegen die Karten des ersten Zyklus nach 10, 20, 30, 40, 50, 60, 70 ... Mischungen in ihren Ausgangspositionen, die des zweiten Zyklus nach 14, 28, 42, 56, 70 ... Mischungen. Die erste Zahl, die diesen beiden Reihen gemeinsam ist, das kleinste gemeinsame Vielfache von 10 und 14, ist 70. Nach dem 70. Mischakt liegen alle Karten wieder so wie am Anfang.

Gibt es einen Zusammenhang zwischen der Größe des Kartenspiels und der Anzahl der Mischakte, nach denen die ursprüngliche Ordnung wiederkehrt? Daß beide Zahlen gleich sind, wie im Falle der zehn Karten, ist untypisch. Bei 4, 6, 8, 10, 12, 14, 16, 18, 20, 22 und 24 Karten braucht man 4, 3, 6, 10, 12, 4, 8, 18, 6, 11 beziehungsweise 20 Einmisch-Runden. Darin liegt durchaus ein Gesetz – aber Sie müssen schon Zahlentheoretiker sein, um es zu entdecken!

Nehmen wir noch einmal das Beispiel mit 10 Karten. Die Tabelle oben zeigt aufeinanderfolgende Zweierpotenzen und die Reste dieser Potenzen beim Teilen durch 11 (die Anzahl n der Karten plus 1). Dieser Rest ist für die zehnte Zweierpotenz gleich 1 – und die Anzahl der Mischrunden bis zur Wiederkehr der Ausgangsreihenfolge ist 10. Bei einem Spiel mit 8 Karten sehen wir uns die Reste an, welche die Zweierpotenzen lassen, wenn man sie durch 9 teilt. Bei der sechsten Zweierpotenz ist dieser Rest gleich 1, und sechs ist die Anzahl der Mischrunden bis zur Wiederkehr.

Diese Regel gilt ganz allgemein. Die Anzahl der Schritte bis zum Rest 1 ist gleich der Anzahl der Einmischrunden bis zur Wiederkehr der Ausgangsfolge. Und diese Zahl ist stets kleiner oder gleich der Anzahl der Karten. Da Ausmischen dasselbe ist wie Einmischen mit zwei Karten weniger, gilt dafür eine ähnliche Regel, nur ist durch n-1 statt n+1 zu dividieren.

Bei dem üblichen Spiel mit 52 Karten muß man 52mal einmischen, um wie durch ein Wunder die Ausgangsfolge wiedererscheinen zu lassen, aber nur achtmal ausmischen. Dieses theoretische Ergebnis ist allerdings praktisch kaum zu realisieren. Selbst unter professionellen Zauberkünstlern gilt perfektes Einmischen als schwierig, und die mehrfache fehlerfreie Ausführung ist fast unmöglich. Ein- oder Aussortieren ist einfacher, und die Anzahl der Schritte ist vorwärts wie rückwärts die gleiche.


Aus: Spektrum der Wissenschaft 7 / 1999, Seite 108
© Spektrum der Wissenschaft Verlagsgesellschaft mbH

Lesermeinung

Beitrag schreiben

Wir freuen uns über Ihre Beiträge zu unseren Artikeln und wünschen Ihnen viel Spaß beim Gedankenaustausch auf unseren Seiten! Bitte beachten Sie dabei unsere Kommentarrichtlinien.

Tragen Sie bitte nur Relevantes zum Thema des jeweiligen Artikels vor, und wahren Sie einen respektvollen Umgangston. Die Redaktion behält sich vor, Leserzuschriften nicht zu veröffentlichen und Ihre Kommentare redaktionell zu bearbeiten. Die Leserzuschriften können daher leider nicht immer sofort veröffentlicht werden. Bitte geben Sie einen Namen an und Ihren Zuschriften stets eine aussagekräftige Überschrift, damit bei Onlinediskussionen andere Teilnehmer sich leichter auf Ihre Beiträge beziehen können. Ausgewählte Lesermeinungen können ohne separate Rücksprache auch in unseren gedruckten und digitalen Magazinen veröffentlicht werden. Vielen Dank!