On an Erdős-Szekeres Game

Der Artikel untersucht ein von der Erdős-Szekeres-Theorem inspiriertes Zweipersonen-Permutationsspiel und bestimmt für den Fall $a \geq b$ sowie $b \in \{2,3,4,5\}$ den Gewinner sowie eine Gewinnstrategie.

Das Wesentliche

Hier ist eine einfache Erklärung der wissenschaftlichen Arbeit von Lara Pudwell, verpackt in eine Geschichte mit Analogien, damit jeder sie verstehen kann.

🎲 Das große Zahlen-Spiel: Wer macht den letzten Fehler?

Stell dir vor, du spielst ein spannendes Brettspiel mit einem Freund. Das Spiel basiert auf einer berühmten mathematischen Regel aus dem Jahr 1935, die besagt: Wenn du genug Zahlen hast, musst du früher oder später eine aufsteigende oder absteigende Reihe finden.

In diesem Spiel geht es darum, wer zuerst diese Reihe vervollständigt. Aber hier ist der Haken: Wer die Reihe vervollständigt, verliert! (Das nennt man im Fachjargon "Misere-Regel", aber denk einfach an "Wer zuerst den Fehler macht, geht nach Hause").

🧩 Die Spielbühne: Ein unsichtbares Raster

Normalerweise spielen die Leute mit Zahlenkarten (1, 2, 3...). Aber die Autorin, Lara Pudwell, hat eine geniale Idee: Sie verwandelt das Spiel in ein Brett mit einem Gitter.

Stell dir ein Gitter vor, das wie ein Schachbrett aussieht, aber nur aus leeren Feldern besteht.

• Die Spieler nehmen sich abwechselnd ein Feld.
• Wenn ein Spieler ein Feld nimmt, werden alle Felder links davon und oberhalb davon automatisch "gesperrt" (wie ein Schatten, der fällt).
• Man darf nur ein Feld wählen, das direkt an den bereits gespielten Feldern angrenzt.

Die Analogie: Stell dir vor, ihr baut eine Mauer aus Ziegeln. Jeder legt einen Ziegel. Aber sobald ein Ziegel gelegt ist, wird der ganze Bereich links und oben davon "eingestürzt" und kann nicht mehr benutzt werden. Das Ziel ist es, den allerletzten Ziegel in der unteren rechten Ecke zu legen. Wer das tut, hat gewonnen, weil der Gegner dann gezwungen ist, eine verbotene Zahlenreihe zu bilden.

🏆 Die Strategie: Wer gewinnt?

Die Forscherin hat herausgefunden, wie man dieses Spiel gewinnt, wenn man bestimmte Regeln beachtet (wenn die Zahl $b$ klein ist, also 2, 3, 4 oder 5).

1. Fall $b=2$ (Das einfache Spiel):
   Das Gitter ist nur eine einzige Zeile lang. Es ist wie ein Wettlauf auf einer geraden Strecke.

   • Die Regel: Wenn die Strecke eine ungerade Länge hat, gewinnt der zweite Spieler. Wenn sie gerade ist, gewinnt der erste. Es kommt also nur darauf an, ob die Zahl $a$ gerade oder ungerade ist.

2. Fall $b=3$ (Das Labyrinth):
   Jetzt hat das Gitter zwei Zeilen. Der erste Spieler hat hier einen klaren Vorteil.

   • Die Strategie: Der erste Spieler spielt so, dass er immer das Gleichgewicht hält. Wenn der Gegner in die untere Zeile springt, springt der erste Spieler in die obere Zeile (und umgekehrt). Es ist wie ein Tanz, bei dem der erste Spieler immer einen Schritt voraus ist und den Gegner in eine Ecke drängt, aus der es kein Entrinnen gibt.

3. Fall $b=4$ und $b=5$ (Der komplexe Tanz):
   Hier wird es schwieriger. Das Gitter hat drei oder vier Zeilen. Die Muster sind komplizierter.

   • Die Entdeckung: Die Autorin hat mit Hilfe von Computern herausgefunden, dass es bestimmte "sichere Zustände" gibt. Stell dir vor, das Spielfeld ist ein Zimmer mit vielen Möbeln. Der erste Spieler versucht immer, das Zimmer so zu ordnen, dass es einem von sieben bestimmten Mustern entspricht (z. B. "die erste Reihe hat eine ungerade Anzahl an freien Plätzen").
   • Egal, was der Gegner macht, der erste Spieler kann immer einen Zug finden, der das Muster wiederherstellt. Am Ende bleibt dem Gegner nur noch eine schlechte Wahl, und der erste Spieler gewinnt.

💡 Warum ist das wichtig?

Früher haben Mathematiker versucht, dieses Spiel nur mit Zahlen zu analysieren. Das war wie der Versuch, ein komplexes Puzzle zu lösen, indem man nur die Farbe der Teile betrachtet. Lara Pudwell hat jedoch das Gitter eingeführt.

• Der Vorteil: Das Gitter macht das Spiel sichtbar. Man sieht die "Schatten" (die gesperrten Bereiche) sofort. Es ist wie der Unterschied zwischen einem Textbuch und einem 3D-Modell.
• Die Erkenntnis: Sie hat gezeigt, dass der erste Spieler fast immer gewinnt (wenn $b$ zwischen 3 und 5 liegt), und sie hat eine Strategie geliefert, wie man das macht. Für noch größere Zahlen ($b \ge 6$) ist das Spiel noch nicht vollständig gelöst, aber die Methode funktioniert als guter Startpunkt.

🚀 Zusammenfassung für den Alltag

Stell dir das Spiel wie ein Schachspiel vor, bei dem du nicht den König fangen musst, sondern verhindern musst, dass dein Gegner eine bestimmte Linie bildet.

• Die Autorin hat ein neues Brett erfunden, auf dem man das Spiel viel besser sehen kann.
• Sie hat Gewinnpläne für verschiedene Brettgrößen entwickelt.
• Die Botschaft: Mit der richtigen Strategie (dem richtigen "Schattenwurf" auf dem Gitter) kann man den Gegner so lange an der Nase herumführen, bis er keine gute Wahl mehr hat und automatisch verliert.

Es ist ein Beweis dafür, dass Mathematik nicht nur trockene Formeln ist, sondern ein Spiel mit klaren Regeln, bei dem man durch cleveres Denken immer einen Schritt voraus sein kann.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des Papers „On an Erdős-Szekeres Game" von Lara Pudwell auf Deutsch.

1. Problemstellung

Das Paper untersucht ein Zwei-Spieler-Strategiespiel, das auf dem berühmten Erdős-Szekeres-Theorem aus dem Jahr 1935 basiert. Das Theorem besagt, dass jede Permutation der Länge $n \ge (a-1)(b-1) + 1$ entweder eine monoton steigende Teilfolge der Länge $a$ oder eine monoton fallende Teilfolge der Länge $b$ enthält.

Das untersuchte Spiel (ein „Permutation Game") läuft wie folgt ab:

• Spieler: Zwei Spieler (Spieler 1 und Spieler 2) ziehen abwechselnd.
• Ablauf: In jedem Zug wählt ein Spieler eine neue Zahl aus $\{1, \dots, n+1\}$ und fügt sie an das Ende der aktuellen Permutation $\pi$ an.
• Ziel (Misère-Spiel): Der erste Spieler, der eine Permutation erzeugt, die entweder eine steigende Teilfolge der Länge $a$ (Muster $I_a$) oder eine fallende Teilfolge der Länge $b$ (Muster $J_b$) enthält, verliert.
• Parameter: Das Spiel wird durch zwei positive ganze Zahlen $a$ und $b$ definiert. Der Fokus liegt auf dem Fall $a \ge b$ und $b \in \{2, 3, 4, 5\}$.

Das Ziel der Arbeit ist es, den Gewinner für diese Parameter zu bestimmen und explizite Gewinnstrategien für Spieler 1 (den ersten Spieler) zu formulieren.

2. Methodik: Das Gitter-Modell (Grid-Shading)

Ein zentraler Beitrag des Papers ist die Transformation des Permutationsspiels in ein visuelles Gitter-Modell, inspiriert vom Beweis des Erdős-Szekeres-Theorems durch Seidenberg (1959).

• Das Spielfeld: Das Spiel wird auf einem Gitter mit $(a-1)$ Spalten und $(b-1)$ Zeilen dargestellt.
• Zellen-Belegung: Für jede Zahl $\pi_i$ in der Permutation wird ein geordnetes Paar $(c, d)$ assoziiert, wobei $c$ die Länge der längsten steigenden Teilfolge ist, die bei $\pi_i$ endet, und $d$ die Länge der längsten fallenden Teilfolge, die bei $\pi_i$ endet.
• Schattierung (Shading): Ein Zug entspricht dem Schattieren der Zelle $(c, d)$.
• Eliminierte Zellen: Wenn eine Zelle $(c, d)$ geschattiert ist, werden alle Zellen $(c', d')$ mit $c' \le c$ und $d' \le d$ als „eliminiert" markiert. Diese Zellen können in zukünftigen Zügen nicht mehr geschattiert werden.
• Spielregeln im Gitter:
  1. Spieler 1 beginnt mit dem Schattieren der Zelle $(1, 1)$.
  2. Jeder folgende Zug muss eine Zelle schattieren, die kantenadjazent zur bereits eliminierten Region liegt.
  3. Der Spieler, der die untere rechte Ecke $(a-1, b-1)$ schattiert, gewinnt (da dies bedeutet, dass das gesamte Board eliminiert ist und der nächste Spieler gezwungen ist, ein verbotenes Muster zu vervollständigen).

Dieses Modell ist äquivalent zu einem Spiel auf einem Chomp-Varianten-Spielbrett und korrespondiert mit den in früheren Arbeiten (Albert et al., 2009) verwendeten ternären Wörtern, bietet jedoch den Vorteil einer geometrischen Anschaulichkeit.

3. Wichtige Beiträge und Ergebnisse

Das Paper liefert Gewinnstrategien für Spieler 1 für den Misère-Fall (Verlierer gewinnt das Muster) bei $a \ge b$ und $b \in \{2, 3, 4, 5\}$.

Fall $b = 2$

• Ergebnis: Der Gewinner hängt von der Parität von $a$ ab.
• Strategie: Das Spielfeld ist ein $1 \times (a-1)$-Gitter. Spieler 1 gewinnt, wenn$a$gerade ist, da Spieler 2 gezwungen ist, die letzte Zelle zu nehmen. Ist$a$ungerade, gewinnt Spieler 2. Dies entspricht dem Erstellen einer rein steigenden Permutation$I_a$.

Fall $b = 3$

• Ergebnis: Spieler 1 hat eine Gewinnstrategie für alle $a \ge 3$.
• Strategie: Das Board ist $2 \times (a-1)$. Spieler 1 kann nach jedem Zug sicherstellen, dass die Anzahl der geschatteten Zellen in Zeile 1 und Zeile 2 in einem spezifischen Verhältnis steht (Zeile 1 hat$i$Zellen, Zeile 2 hat$i-1$Zellen). Durch eine symmetrische Antwort auf die Züge von Spieler 2 zwingt Spieler 1 den Gegner in eine Position, aus der er das Muster$I_a$oder$J_3$ vervollständigen muss.

Fall $b = 4$

• Ergebnis: Spieler 1 hat eine Gewinnstrategie für alle $a \ge 4$.
• Strategie: Das Board ist $3 \times (a-1)$. Da hier mehrere Permutationen zu derselben Board-Konfiguration führen können, wird die Strategie rein auf der Board-Ebene definiert. Spieler 1 hält das Board in zwei möglichen Zuständen (basierend auf der Anzahl der eliminierten Zellen in den Zeilen), unabhängig davon, wie Spieler 2 zieht. Dies wird durch eine Analyse der möglichen Züge und Gegenzüge (Openings, Midgame, Endgame) bewiesen.

Fall $b = 5$ (Neuer Beitrag)

• Ergebnis: Spieler 1 hat eine Gewinnstrategie für alle $a \ge 5$.
• Methodik: Dieser Fall ist deutlich komplexer. Die Strategie wurde durch eine computerunterstützte Analyse entwickelt, bei der alle möglichen Board-Konfigurationen für kleine $a$ klassifiziert wurden (Klasse N für „Next-player win" und Klasse P für „Previous-player win").
• Strategie: Die Strategie definiert eine Menge von sieben spezifischen Board-Zuständen (genannt $\mathcal{S}$), die Spieler 1 anstrebt.
  1. Opening: Spieler 1 führt das Spiel in einen Zustand aus $\mathcal{S}$.
  2. Midgame: Ungeachtet des Zuges von Spieler 2 kann Spieler 1 immer zu einem Zustand in $\mathcal{S}$ zurückkehren.
  3. Endgame: Sobald das Board nahe am Rand ist, navigiert Spieler 1 das Spiel in eine Endzustands-Menge $\mathcal{E}$, aus der ein Gewinn durch „Tit-for-Tat"-Antworten (Spiegelstrategie) garantiert ist.
• Bedeutung: Dies erweitert die bekannten Ergebnisse von Albert et al. (2009), die für $b=5$ keine explizite Strategie für den Misère-Fall lieferten.

4. Weitere Analysen und Diskussion

• Normal Play vs. Misère Play: Das Paper diskutiert auch die Variante, bei der der Spieler, der das Muster vervollständigt, gewinnt (Normal Play). Es wird gezeigt, dass die Strategie für den Normal Play im Wesentlichen der Misère-Strategie entspricht, jedoch auf einem um eine Zeile und eine Spalte verkleinerten Board ($(b-2) \times (a-2)$). Dies bestätigt Vermutungen aus der Literatur, dass Spieler 1 für $b \ge 4$ gewinnt.
• Anzahl der Züge: Es wird analysiert, wie viele Züge das Spiel dauert. Während das Theorem eine Obergrenze von $(a-1)(b-1)+1$ Zügen garantiert, enden die Spiele unter den optimalen Strategien oft deutlich früher (z. B. bei $b=5$ etwa in der Hälfte der maximalen Länge).
• Anzahl der Gewinnpositionen: Eine Tabelle zeigt den Anteil der Board-Konfigurationen, die in der Klasse P (Verliererposition für den nächsten Spieler) liegen. Es wird beobachtet, dass dieser Anteil mit wachsendem $a$ sinkt, aber Paritätseffekte (gerade/ungerade) eine Rolle spielen.

5. Signifikanz und Ausblick

• Theoretische Erweiterung: Das Paper schließt eine Lücke in der Theorie der Permutationsspiele, indem es explizite Gewinnstrategien für $b=5$ im Misère-Fall liefert, was über den Stand der Forschung von 2009 hinausgeht.
• Methodischer Fortschritt: Die Einführung des Gitter-Schattierungsmodells bietet eine intuitive und geometrische Alternative zu den in der Literatur üblichen kombinatorischen Wort-Modellen. Dies erleichtert die Visualisierung und das Verständnis der Spielzustände.
• Herausforderungen für die Zukunft: Die Komplexität der Strategie wächst mit $b$ stark an. Für $b \ge 6$ wird die manuelle Ableitung von Mustern zunehmend unpraktisch, was auf die Notwendigkeit weiterer algorithmischer oder computergestützter Ansätze für allgemeinere $b$-Werte hindeutet.

Zusammenfassend liefert das Paper eine umfassende Analyse des Erdős-Szekeres-Spiels für kleine Parameter $b$, definiert eine neue visuelle Sprache zur Beschreibung des Spiels und beweist die Existenz von Gewinnstrategien für Spieler 1 in Fällen, die zuvor nur vermutet oder nicht vollständig gelöst waren.