Schon die Babylonier der Antike ritzten arithmetische Denksportaufgaben in ihre Tontafeln, um auf spielerische Weise Mathematik zu erklären. Und die ehrwürdige Tradition ist noch sehr lebendig: Gerade in den letzten Jahren ist eine Reihe neuartiger mathematischer Spiele erfunden worden. Eines von ihnen stammt von David Gale von der Universität von Kalifornien in Berkeley. Es kombiniert Ideen aus der Topologie und der Mengenlehre, ist in seinen Regeln sehr überschaubar und dennoch reizvoll; denn bisher hat niemand eine Gewinnstrategie dafür gefunden.

Zunächst eine kurze Erinnerung an die Mengenlehre. Eine Menge ist eine Zusammenfassung verschiedener Gegenstände zu einem Ganzen; diese Gegenstände heißen "Elemente" der Menge. Eine Menge kann unendlich viele Gegenstände enthalten – das ist der für die Mengentheoretiker interessante Fall. Aber die Mengen unseres Spiels sind endlich. Sie enthalten sogar so wenige Elemente, dass man sie eins nach dem anderen aufzählen kann. Die Mathematiker pflegen für solche Auflistungen geschweifte Klammern zu verwenden. Beispielsweise ist {2, 3, 5, 7} die Menge aller Primzahlen unterhalb von 10.

Eine Menge Y heißt eine "Teilmenge" einer Menge X, wenn jedes Element von Y auch Element von X ist: Die Menge {3, 5, 7} aller ungeraden Primzahlen unter 10 ist eine Teilmenge der Menge {2, 3, 5, 7}. Es ist nicht verboten, dass Y alle Elemente von X enthält: Jede Menge ist Teilmenge von sich selbst. Will man diesen Fall ausschließen, spricht man von "echten" Teilmengen. Eine Teilmenge einer Menge X heißt "echt", wenn sie von X verschieden ist. Eine Menge kann auch nur ein einziges Element haben – {2} ist die Menge aller geraden Primzahlen – oder gar keins: Das ist die leere Menge.

Gales Spiel heißt "Teilmengen wegnehmen". Es beginnt mit einer endlichen Menge M. Dabei kommt es nicht darauf an, was die Elemente von M sind. Also nehmen wir der Einfachheit halber die Menge {1, 2, 3, …, n} der natürlichen Zahlen von 1 bis n. Die beiden Spieler ziehen abwechselnd. Wer am Zug ist, wählt eine echte, nichtleere Teilmenge von M, aber so, dass keine bereits früher von einem der beiden Spieler gewählte Menge eine Teilmenge der neu gewählten Menge ist. Wer nicht mehr ziehen kann, hat verloren.

Damit man den Überblick behält, bereitet man zweckmäßig auf einem Blatt Papier eine Tabelle mit n Spalten namens 1 bis n vor. Jeder Zug ergibt eine neue Zeile in der Tabelle; und zwar kennzeichnet der Spieler die Teilmenge, die er wählt, indem er Kreuze in die entsprechenden Spalten einträgt. Ein neuer Zug ist genau dann zulässig, wenn er nicht alle Kreuze einer früheren Zeile enthält.

Nennen wir die beiden Spieler Anton und Berta, wobei Anton derjenige ist, der den ersten Zug hat. Wenn n=1 ist, gibt es keinen zulässigen Zug, also gewinnt Berta. Wenn n=2 ist, haben wir M = {1, 2}. Anton hat die beiden Eröffnungszüge {1} und {2} zur Auswahl, und Berta kann den jeweils anderen Zug wählen. Danach kann Anton nicht mehr ziehen, also gewinnt Berta.

Bei n=3, also M={1, 2, 3}, wird das Spiel allmählich interessanter. Angenommen, Anton wählt eine Teilmenge mit 2 Elementen, etwa {1, 2}. Dann kann Berta die "Komplementmenge" wählen, also alles, was Anton nicht gewählt hat; das ist in diesem Falle die Menge {3}. Nun kann Anton keine Teilmenge mehr wählen, die 3 enthält, sondern muss eine echte Teilmenge von {1, 2} nehmen. Damit befindet er sich in der gleichen Situation wie zu Beginn des Spiels mit {1, 2}, also gewinnt Berta abermals. Das Gleiche gilt, wenn Anton mit irgendeiner anderen zweielementigen Teilmenge eröffnet.

Anton kann als ersten Zug auch eine einelementige Teilmenge wählen, etwa {3}. Wenn aber Berta dann das Komplement {1, 2} wählt, bringt sie Anton wieder in die Anfangsstellung des Spiels mit {1, 2} und gewinnt. Da Anton entweder mit einer einelementigen oder einer zweielementigen Teilmenge beginnen muss, hat Berta eine Gewinnstrategie: Sie wählt stets das Komplement der von Anton gewählten Menge. Ehe Sie weiter lesen, wollen Sie sich vielleicht überlegen, ob Berta mit dieser Strategie auch gewinnt, wenn n größer als 3 ist.

Eine geometrische Veranschaulichung hilft das Spiel zu durchschauen. Wir verwenden dazu Dreiecke und deren Verallgemeinerungen auf höhere (und niedrigere) Dimensionen, die so genannten Simplizes. Wo im Raum die Eckpunkte dieser Gebilde liegen, ist völlig belanglos. Es kommt nur auf die topologischen Beziehungen zwischen Eckpunkten, Kanten. Seitenflächen und so weiter an.

Ein Simplex in n Dimensionen, kurz ein n-Simplex, ist gewissermaßen das einfachste geometrische Gebilde, das nicht in weniger als n Dimensionen passt. Ein 3-Simplex ist ein Tetraeder, dessen Ecken wir mit 1, 2, 3 und 4 bezeichnen (Bild links). Es hat vier Seitenflächen, sechs Kanten und vier Ecken. Die Seitenflächen sind Dreiecke (das sind 2-Simplizes in unserer Terminologie), die Kanten sind Strecken (1-Simplizes), und die Ecken sind Punkte (0-Simplizes). Diese Teile des 3-Simplex entsprechen genau den Teilmengen von {1, 2, 3, 4}. Das Tetraeder selbst gehört zur ganzen Menge {1, 2, 3, 4}, die Seitenflächen zu den dreielementigen Teilmengen {1, 2, 3}, {1, 2, 4}, {1, 3, 4} und {2, 3, 4}. Die Kanten entsprechen den zweielementigen Teilmengen {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4} und {3, 4} und die Ecken den einelementigen Teilmengen {1}, {2}, {3} und {4}.

Allgemein kann man jedes (n–1)-Simplex mit der Menge {1, 2, …, n} identifizieren und seine diversen niederdimensionalen Teile mit deren echten Teilmengen. Das Spiel "Teilmengen wegnehmen" kann man nun als "Simplex demontieren" umformulieren. Das Spiel beginnt mit einem vollständigen Simplex. Ein Zug besteht darin, ein echtes Teilsimplex beliebiger Dimension zu wählen und sein Inneres wegzunehmen, dazu das Innere aller höherdimensionalen Simplizes, die das gewählte Simplex enthalten. Es werden also alle Teilmengen (Teilsimplizes) weggenommen, die in der Zukunft als Züge nicht mehr verwendet werden dürfen. Aber die Ränder des gewählten Teilsimplex werden nicht demontiert: Wenn eine Dreiecksfläche gewählt wird, bleiben ihre Kanten erhalten.

Schauen wir uns "Simplex demontieren" für ein 3-Simplex an, entsprechend "Teilmengen wegnehmen" für n=4. Die Ausgangssituation ist ein vollständiges 3-Simplex, also ein Tetraeder. Das Bild auf der vorigen Seite zeigt eine erlaubte Zugfolge. Eine systematische Betrachtung aller solcher Zugfolgen zeigt, dass Berta das Spiel mit n=4 stets gewinnen kann. Das Gleiche gilt für n=5 und n=6. Gale vermutet, dass es für jeden Wert von n eine Gewinnstrategie für Berta gibt. Soweit ich weiß, ist das bisher weder bewiesen noch widerlegt worden.

Wie kann Bertas Gewinnstrategie für n=4, 5, 6 und höhere Werte aussehen? Sollte sie das Rezept mit dem Komplement, das für n=3 funktioniert, weiterverfolgen? Wenn n=4 ist, kann Anton mit einer Ecke, einer Kante oder einer Dreiecksseite beginnen. Wenn er eine Ecke wählt und Berta deren Komplement, reduziert sich das Spiel auf den Fall n=3, und Berta gewinnt. Das Gleiche geschieht, wenn er eine Dreiecksfläche wählt und und Berta die komplementäre Ecke. Aber was geschieht, wenn Anton eine Kante wählt, sagen wir die Kante zu {1, 2}, und Berta die komplementäre Kante, also {3, 4}?

Wenn Anton im nächsten Zug {3} wählt, kann Berta nicht die komplementäre Teilmenge {1, 2, 4} wählen, denn das wäre kein zulässiger Zug: Diese Dreiecksfläche ist schon verschwunden (Bild links). Die "Komplementärstrategie" funktioniert also nicht. Einige Mathematiker haben die Vermutung ausgesprochen, dass für alle n die Komplementärstrategie immerhin Bertas richtige Antwort auf den Eröffnungszug von Anton ist, auch wenn sie, wie wir gesehen haben, später von dieser Strategie möglicherweise abgehen muss.

Aber wie steht es nun für den armen Anton? Ist es wirklich so, dass Berta ihn in Teilmengen wegnehmen für alle n schlagen kann? Für n=7, 8 oder andere kleine Werte bekommt man das wahrscheinlich heraus, indem man einen Computer sämtliche denkbaren Möglichkeiten erschöpfend durchsuchen lässt. Für größere n aber werden neue Ideen erforderlich sein. Schicken Sie der Redaktion Ihre Überlegungen! Interessante Ergebnisse werden in einem Nachtrag veröffentlicht.

Literaturhinweis

Games of No Chance. Von R. J. Nowakowski (Hg.). Cambridge University Press, 1996.

Aus: Spektrum der Wissenschaft 10 / 2000, Seite 114
© Spektrum der Wissenschaft Verlagsgesellschaft mbH