Direkt zum Inhalt

Zahlen wegnehmen

In einem Spiel mit 100 Karten hat gewonnen, wer seinen Gegner dazu bringt, die Nummer 1 zu wählen. Wie schafft man das? Und wie geht man bei einer beliebigen Anzahl von Karten vor?

Vor etwa zwei Jahren erzählte mir Ian Porteous, ein Mathematiker an der Universität Liverpool, von einem Spiel, mit dem sein Sohn Rob seinen Schülern das Einmaleins nahebringt. Es heißt Juniper Green nach der Schule, an der Rob Porteous unterrichtet. Zwei Kinder spielen gegeneinander, die Regeln sind einfach, der Zufall spielt keine Rolle, und es gibt keine Geheimnisse wie etwa verdeckte Karten. Also existiert – nach einem Satz der mathematischen Spieltheorie – eine Gewinnstrategie: Einer der Spieler kann den Sieg erzwingen, einerlei was der andere tut.
Diese Strategie zu finden ist freilich alles andere als einfach. Immerhin hielt es der Mathematiker und Physiker Eugene P. Wigner (1902 bis 1995; Physik-Nobelpreis 1963) Ende der dreißiger Jahre nicht für unter seiner Würde, das Spiel in einer Zahlentheorie-Vorlesung an der Universität Princeton (New Jersey) zu diskutieren und eine Gewinnstrategie zu ermitteln. Rob Porteous ist also nicht der Erstentdecker.
Für Juniper Green braucht man 100 durchnumerierte Karten. Zu Beginn des Spiels sind sie mit den Zahlen nach oben auf den Tisch zu legen, am besten geordnet in Zehnerreihen, damit man jede Karte mühelos findet. Die Regeln sind:
1. Die beiden Spieler nehmen abwechselnd jeweils eine Karte vom Tisch. Die entfernten Karten werden nicht ersetzt und im weiteren Verlauf nicht mehr verwendet.
2. Außer im ersten Zug muß die gewählte Zahl ein Teiler oder ein Vielfaches der zuletzt gezogenen sein.
3. Wer keine Karte mehr wählen kann, hat verloren.
Eine weitere Regel gibt es noch, damit das Spiel überhaupt interessant wird. Wenn der erste Spieler im Eröffnungszug eine Primzahl größer als 50 wählen dürfte, wäre ihm damit der Sieg bereits sicher. Nennen wir die beiden Spieler Alice und Bob – nach den Konventionen der Kryptographen, auch wenn es diesmal keine Geheimnisse auszutauschen gibt. Wenn Alice das Spiel mit 97 eröffnet, bleibt Bob nichts übrig, als 1 zu nehmen. Nun wählt Alice eine weitere große Primzahl, zum Beispiel 89. Dann kann Bob nicht mehr ziehen, denn die Eins ist schon vom Tisch. Um diese primitive Strategie auszuschließen, lautet die letzte Regel:
4. Im Eröffnungszug muß eine gerade Zahl gewählt werden.
Selbst mit dieser Einschränkung behalten die großen Primzahlen eine wichtige Rolle (wobei hier "groß" nichts weiter bedeutet als "größer als 50"). An ihnen liegt es nämlich, daß ein Spieler, der die Karte 1 nimmt, verliert – zumindest wenn sein Gegner aufpaßt. Auf 1 von Bob antwortet Alice mit einer großen Primzahl, zum Beispiel 97 (die muß noch im Spiel sein, denn sie kann überhaupt nur gewählt werden, wenn der vorige Zug 1 war). Nun hat Bob keinen Zug mehr zur Verfügung.
Das Bild zeigt den Verlauf einer denkbaren, beiderseits nicht besonders raffiniert gespielten Partie. Ich schlage vor, daß Sie jetzt das Lesen unterbrechen, sich einen Satz Karten zurechtmachen und ein paar Spiele probieren. Ich werde Ihnen nicht den Spaß verderben, indem ich Ihnen die Gewinnstrategie verrate.
Statt dessen analysiere ich die Variante mit 40 Karten; das wird Ihnen für das Originalspiel ein wenig weiterhelfen. Für sehr kleine Kinder ist das Spiel mit nur 20 Karten geeigneter. Der Einfachheit halber kürze ich Juniper Green mit n Karten als JG-n ab; es geht im folgenden also um eine Gewinnstrategie für JG-40.
Auf manche Eröffnungen folgt sehr schnell die Niederlage. Ein Beispiel:
ZugAliceBob
138
219
31
437
5verliert
Nicht anders geht es mit dem Eröffnungszug 34. Einige weitere Zahlen sind gleichfalls fatal, nicht nur als Eröffnungszüge, sondern überhaupt. Wenn Alice so ungeschickt wäre, 5 zu spielen, kann Bob 25 ziehen, und Alice bleibt nichts übrig, als 1 zu nehmen und damit zu verlieren. (Karte 25 muß noch verfügbar sein, denn die einzigen möglichen Vorgänger – in JG-40 – sind 1 und 5.)
Andersherum wäre es für Alice also günstig, wenn sie Bob zwingen könnte, 5 zu spielen. Kann sie das erreichen? Nun, wenn Bob 7 zieht, kann sie so hoch kontern, daß ein Vielfaches nicht zur Verfügung steht; in diesem Falle 35. Das läßt Bob nur noch die Wahl zwischen 1 und 5; in beiden Fällen verliert er. Na gut; aber kann sie Bob dazu zwingen, 7 zu spielen? Ja, wenn er vorher 3 genommen hat. Dann kann sie nämlich 21 ziehen, worauf er mit 7 antworten muß. Und wie bringt sie Bob dazu, 3 zu spielen? Nun, wenn er 13 wählt, verdreifacht sie auf 39.
So kann Alice beliebig weiterdenken: Sie baut rückwärts von Bobs Verlustpositionen aus hypothetische Spielverläufe auf, in denen jeder Zug von Bob erzwungen ist und dadurch seine Niederlage unausweichlich macht.
Aber kann sie Bob von Anfang an auf diese abschüssige Bahn bringen? Die vierte Regel verlangt zu Beginn des Spiels eine geradzahlige Karte; deshalb liegt die Vermutung nahe, daß der 2 eine Schlüsselrolle zukommt. Das ist tatsächlich der Fall: Wenn Bob 2 spielt, antwortet Alice mit 26 und zwingt ihn damit in die Falle mit der 13. Wie aber kann Alice erzwingen, daß Bob die 2 wählt?
Die Antwort ist: Das muß gar nicht sein. Aber 2 ist trotzdem der Schlüssel zu einer Gewinnstrategie: Alice eröffnet mit 22. Dann spielt Bob entweder 2 und gerät in die dargestellte erzwungene Zugfolge, oder er spielt 11. Nun hat Alice die Wahl zwischen 1 (womit sie verlieren würde) und 33. Auf letztere hin muß Bob 3 spielen, denn 33 ist schon weg, und Alice kann gewinnen.
Die folgende Tabelle faßt Alices Strategie zusammen. Die beiden Spaltenpaare entsprechen den Alternativen, die Bob hat (die Zugmöglichkeit 1 ist in keinem Falle aufgeführt):
ZugAliceBobAliceBob
126
2132
33922
4311
52133
673
73521
857
92535
10verliert5
1125
12verliert
Es gibt noch mindestens einen weiteren Eröffnungszug für Alice, mit dem sie sicher gewinnen kann: 26. Es entwickelt sich im wesentlichen dasselbe Spiel, wobei die Reihenfolge einiger Züge vertauscht ist:
ZugAliceBobAliceBob
122
2112
33326
4313
52139
673
73521
857
92535
10verliert5
1125
12verliert
Offenbar kommt es besonders auf die beiden Primzahlen 11 und 13 an. Ist der Eröffnungszug das Doppelte einer solchen Zahl (22 oder 26), muß Bob entweder mit 2 antworten – worauf Alice gewinnen kann – oder mit der Primzahl selbst. Aber dann antwortet Alice mit dem Dreifachen der Primzahl, so daß Bob 3 nehmen muß, und wieder ist sie auf der Gewinnerstraße. Die Strategie funktioniert, weil es außer dem Doppelten nur noch genau ein weiteres Vielfaches der Primzahl gibt, das unter 40 liegt, nämlich 33 beziehungsweise 39. Es sind also diese mittelgroßen Primzahlen – zwischen einem Viertel und einem Drittel der Maximalzahl –, die einen Sieg garantieren.
Gibt es außer 22 und 26 noch einen gewinnsicheren Eröffnungszug? Das herauszufinden überlasse ich Ihnen. Außerdem sollten Sie jetzt JG-100 oder sogar JG-1000 analysieren können. Gibt es bei diesen Varianten eine unschlagbare Strategie für den ersten Spieler?
Vielleicht hilft Ihnen für JG-100 ein Hinweis von Michael D. Tibbetts aus Clearwater (Florida). Er bemerkte, daß es in allen Aspekten des Spiels auf Primzahlen ankommt, und bildete vier Gruppen: große (53 und höher), mittelgroße (37, 41, 43, 47), mittlere (29, 31) und kleine (17, 19). Zweimal eine mittlere Primzahl ist eine gewinnträchtige Eröffnung.
Damit sind wir gut vorbereitet, das Problem in aller Allgemeinheit zu stellen. Man betrachte JG-n für eine beliebige natürliche Zahl n. Da es nach den Regeln kein Unentschieden geben kann, folgt aus allgemeinen Sätzen der Spieltheorie, daß es entweder für Alice – die beginnt – oder für Bob eine Gewinnstrategie gibt. Nennen wir die Zahl n primär, falls in JG-n Alice im Vorteil ist, und sekundär im anderen Fall. Können Sie sagen, welche n primär sind und welche sekundär?
Für die ersten n zeigen einige schnelle Berechnungen, daß 3 und 8 primär sind, hingegen 2, 4, 5, 6, 7 und 9 sekundär. Die Zahl 1 ist aus trivialen Gründen sekundär, denn es gibt keinen zulässigen Eröffnungszug; also verliert Alice im ersten Zug. Wie steht es mit 100? Und wie mit allgemeinen n?
Wer ein allgemeines Muster findet und beweisen kann, hat Anlaß zum Stolz. Das Kriterium, das Eugene P. Wigner fand, ist nämlich nicht gerade einfach. Es kommt darauf an, ob gewisse Primzahlen in der Primfaktorzerlegung von n!=1×2×...×n eine gerade oder eine ungerade Anzahl von Malen vorkommen.


Aus: Spektrum der Wissenschaft 3 / 1998, Seite 8
© 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!