In Kooperation mit

Job & Karriere

Rätsel der Woche Jeder Strich ein Punkt

Vor 55 Jahren erfanden zwei Mathematik-Liebhaber ein einfaches Spiel für Stift und Papier. Haben Sie bei »Sprouts« den Durchblick?
Foto:

DER SPIEGEL

Die Regeln sind simpel: Auf einem Blatt Papier befinden sich n Punkte. Diese werden abwechselnd von zwei Spielern durch Linien miteinander verbunden. Die Linien dürfen sich nicht kreuzen. Und es kommt mit jedem Spielzug auch immer ein neuer Punkt hinzu.

»Sprouts« , auf Deutsch: Sprosse, heißt das Spiel, das sich der Mathematiker John Conway und der Informatiker Michael Paterson Anfang 1967 ausgedacht haben. Bald wurde auch der Rätselsammler Martin Gardner darauf aufmerksam und machte »Sprouts mit seiner Kolumne im »Scientific American«  einem größeren Publikum bekannt.

In einer einfachen Variante startet man das Spiel mit nur zwei Punkten – siehe Zeichnung unten. Ein Spielzug besteht entweder darin, einen Punkt mit sich selbst zu verbinden (A) – oder zwei Punkte miteinander zu verbinden (B). In beiden Fällen wird in die Mitte der neu gezeichneten Verbindung ein neuer Punkt gesetzt, der in der Zeichnung blau hervorgehoben ist.

Foto: DER SPIEGEL

Abwechselnd fügen die beiden Spieler jeweils eine neue Linie hinzu. Linien dürfen einander nicht kreuzen. Und ganz wichtig: Von einem Punkt dürfen höchstens drei Linien ausgehen. Gewinner beziehungsweise Gewinnerin ist, wer als letzter eine Linie zeichnen kann.

Anzeige
Dambeck, Holger

Blind Date mit zwei Unbekannten: 100 neue Mathe-Rätsel (Aus der Welt der Mathematik, Band 4)

Verlag: KiWi-Taschenbuch
Seitenzahl: 256
Für 11,00 € kaufen

Preisabfragezeitpunkt

28.01.2023 09.11 Uhr

Keine Gewähr

Produktbesprechungen erfolgen rein redaktionell und unabhängig. Über die sogenannten Affiliate-Links oben erhalten wir beim Kauf in der Regel eine Provision vom Händler. Mehr Informationen dazu hier

Offenbar dauert eine Runde »Sprouts« nicht unendlich lang. Sonst gäbe es ja keinen Sieger.

Die Frage ist: Wie viele Spielzüge kann ein Spiel mit n Punkten höchstens haben?

Eine Runde »Sprouts« mit n Punkten ist nach höchstens 3n-1 Spielzügen vorbei.

Auf den ersten Blick erscheint das Spiel unübersichtlich: Bei jedem Zug kommt ein neuer Punkt hinzu. Auch die konkrete Linienführung dürfte beeinflussen, wie schnell ein Spiel zu Ende ist.

Die Lösung ist dann allerdings verblüffend einfach: Von einem Punkt können maximal drei Linien ausgehen. Ist die Zahl von drei Linien erreicht, ist der Punkt tot – er kann im Spiel nicht weiter genutzt werden. Die Höchstzahl an Zügen wird erreicht, wenn möglichst alle n Punkte tot sind, weil dort jeweils drei Linien beginnen.

Vor dem ersten Spielzug gibt es keine einzige Linie. An jedem Punkt der n Punkte könnten drei Linien beginnen – das sind insgesamt 3n abgehende Linien. Bei einem Spielzug sinkt die Zahl möglicher abgehender Linien um 2, denn es wird eine Linie gezogen, die zwei Punkte verbindet oder einen Punkt mit sich selbst.

Bei einem Spielzug kommt jedoch auch ein neuer Punkt hinzu. Dieser liegt in der Mitte der neuen Linie – von ihm kann also nur noch eine neue Linie abgehen. Deshalb verringert sich die Zahl möglicher, von Punkten abgehenden Linien pro Spielzug um 2-1 = 1.

Zum Start gibt es 3n mögliche Linienanfänge. Nach 3n-1 Spielzügen kann höchstens noch ein einziger Punkt existieren, von dem eine Linie beginnen kann. Dann ist kein weiterer Spielzug mehr möglich. Das Spiel endet also nach höchstens 3n-1 Zügen.

Tatsächlich kann es auch schon früher enden, weil zwei Punkte, von denen jeweils höchstens zwei Linien abgehen, nicht miteinander verbunden werden können. Das passiert, wenn einer oder beide Punkte von Linien vollständig umschlossen sind und der andere Punkt außerhalb liegt.

Wer aber kann bei »Sprouts« gewinnen – Spieler 1 oder Spieler 2? Gibt es eine allgemeingültige Strategie? Mathematiker haben »Sprouts« eingehend untersucht – auch mit Computerhilfe. Demnach kann Spieler 2 für 1, 2, 6, 7, 8 und 12 Startpunkte immer gewinnen. Spieler 1 hat hingegen bei 3, 4, 5, 9, 10 und 11 Startpunkten sichere Siegchancen.

Die Vermutung ist, dass der Rest, den die Startpunktezahl bei Teilen durch 6 lässt, darüber entscheidet, wer das Spiel gewinnen kann. Bei einem Rest von 3, 4 oder 5 existiert für Spieler 1 eine Gewinnstrategie. In den anderen Fällen kann Spieler 2 gewinnen. Einen Beweis dafür haben Mathematiker offenbar bislang nicht. Es gibt nur Computeranalysen , welche die Vermutung für alle Zahlen bis 44 bestätigen sowie auch für n = 46, n = 47 und n = 53. Das einfache Spiel für Stift und Papier von Conway und Paterson ist dann doch nicht ganz so einfach.

Sollten Sie ein Rätsel aus den vergangenen Wochen verpasst haben – hier sind die jüngsten Folgen:

Anzeige
Dambeck, Holger

Kommen drei Logiker in eine Bar...: Die schönsten Mathe-Rätsel (Aus der Welt der Mathematik, Band 3)

Verlag: KiWi-Taschenbuch
Seitenzahl: 240
Für 9,99 € kaufen

Preisabfragezeitpunkt

28.01.2023 09.11 Uhr

Keine Gewähr

Produktbesprechungen erfolgen rein redaktionell und unabhängig. Über die sogenannten Affiliate-Links oben erhalten wir beim Kauf in der Regel eine Provision vom Händler. Mehr Informationen dazu hier
Die Wiedergabe wurde unterbrochen.