Experimenting with Permutation Wordle

Diese Arbeit untersucht die Vermutung von Kutin und Smithline zur Optimalität der „zyklischen Verschiebungs"-Strategie beim Permutations-Wordle, indem sie die Spielstrategie formalisiert, experimentelle Analysen durchführt und die Koeffizienten einer induktiven erzeugenden Funktion untersucht.

Das Wesentliche

Hier ist eine einfache Erklärung der Forschungsarbeit von Aurora Hiveley, die sich mit einem mathematischen Spiel namens „Permutation Wordle" beschäftigt.

Das Spiel: Ein Rätsel mit vertauschten Schuhen

Stellen Sie sich vor, Sie haben einen Schrank mit n verschiedenen Schuhen, nummeriert von 1 bis n. Ein „Meister" hat diese Schuhe in einer bestimmten Reihenfolge in den Schrank gestellt, aber er verrät Ihnen die Reihenfolge nicht.

Ihr Ziel: Finden Sie die richtige Reihenfolge heraus.

• Sie dürfen einen Versuch wagen (eine „Vermutung").
• Der Meister sagt Ihnen dann nur: „Welche Schuhe stehen an der richtigen Stelle?" (Er verrät Ihnen nicht, welche Schuhe falsch sind, nur welche sitzen perfekt).
• Wenn alle Schuhe sitzen, haben Sie gewonnen.

Das Problem: Wie können Sie die richtige Reihenfolge in so wenigen Versuchen wie möglich erraten?

Die große Frage: Gibt es den perfekten Trick?

Zwei Mathematiker, Kutin und Smithline, haben einen speziellen Trick vorgeschlagen, den sie „Zyklische Verschiebung" nennen.

Der Trick funktioniert so:

1. Sie raten eine Reihenfolge.
2. Der Meister sagt Ihnen, welche Schuhe sitzen.
3. Alle Schuhe, die nicht sitzen, schieben Sie einen Schritt nach rechts in den nächsten freien Platz. Die Schuhe, die schon sitzen, lassen Sie unberührt.
4. Sie wiederholen das, bis alles passt.

Die große Frage der Mathematiker war: Ist dieser Trick der absolut beste? Gibt es einen besseren Weg, um das Spiel schneller zu gewinnen?

Was hat Aurora in diesem Papier untersucht?

Aurora Hiveley hat sich dieses Problem angesehen und versucht, die Frage zu beantworten, ob der „Zyklische Verschiebung"-Trick wirklich der König aller Strategien ist.

Stellen Sie sich vor, Sie bauen eine Maschine, die das Spiel spielt. Diese Maschine hat verschiedene „Gehirn-Teile" (Strategien), die entscheiden, wie sie bei 2 Schuhen, 3 Schuhen oder 10 Schuhen vorgeht.

1. Der erste Test: Der Durchschnitt

Aurora hat mit einem Computer (einem Programm namens Maple) Millionen von Spielen simuliert.

• Ergebnis: Bis zu einer gewissen Größe (bei 7 oder 8 Schuhen) hat sich bestätigt: Der Trick der „Zyklischen Verschiebung" ist tatsächlich sehr stark. Er gewinnt im Durchschnitt schneller als andere zufällige Tricks.

2. Der tiefe Blick: Die „Generierende Funktion" als Kristallkugel

Da man nicht unendlich viele Spiele simulieren kann, hat Aurora eine mathematische „Kristallkugel" benutzt, die man in der Mathematik generierende Funktion nennt.

• Die Analogie: Stellen Sie sich diese Funktion wie ein Rezeptbuch vor. Jedes Kapitel des Buches (ein Koeffizient) sagt Ihnen: „Wie viele verschiedene Schuh-Reihenfolgen kann ich mit genau 1, 2 oder 3 Versuchen erraten?"
  • Kapitel 1: Wie viele kann ich beim ersten Versuch erraten? (Nur 1: Die perfekte Reihenfolge).
  • Kapitel 2: Wie viele kann ich beim zweiten Versuch erraten?
  • Kapitel 3: Wie viele kann ich beim dritten Versuch erraten?

Aurora hat bewiesen, dass das „Zyklische Verschiebung"-Rezeptbuch für das dritte Kapitel (also Spiele, die in genau 3 Versuchen enden) die meisten Einträge hat. Das bedeutet: Mit diesem Trick haben Sie die größte Chance, das Rätsel in genau 3 Versuchen zu lösen, verglichen mit allen anderen Tricks, die sie getestet hat.

3. Der „Schlechte" Trick

Sie hat auch einen Gegen-Trick untersucht, bei dem man die Schuhe nach links schiebt (statt nach rechts). Dieser Trick war deutlich schlechter. Es war, als würde man versuchen, einen Schlüssel in ein Schloss zu drehen, aber immer in die falsche Richtung.

Die wichtigsten Erkenntnisse (in einfachen Worten)

1. Der Trick ist stark: Die Methode, bei der man die falschen Elemente nach rechts schiebt, ist für Spiele, die in 1, 2 oder 3 Versuchen enden, mathematisch bewiesen die beste Strategie.
2. Es ist nicht trivial: Man könnte denken, „irgendeine" Verschiebung sei egal. Aber Aurora hat gezeigt, dass die Art der Verschiebung (z. B. ob man Nachbarn vertauscht oder alle nach rechts schiebt) einen riesigen Unterschied macht.
3. Die Grenzen: Die Beweise in diesem Papier gelten nur für Spiele, die sehr schnell enden (maximal 3 Versuche). Was passiert, wenn das Spiel 4, 5 oder 10 Versuche dauert? Das ist noch ein Rätsel. Die Mathematik wird dort viel komplizierter, wie ein Labyrinth, das immer enger wird.

Fazit

Aurora Hiveley hat gezeigt, dass der von Kutin und Smithline vorgeschlagene „Zyklische Verschiebung"-Trick für kurze Spiele der unangefochtene Champion ist. Sie hat das nicht nur durch Ausprobieren bewiesen, sondern durch eine elegante mathematische Analyse, die wie ein Mikroskop funktioniert, um zu sehen, welche Strategie die meisten „Gewinner"-Szenarien in der Zukunft vorhersagt.

Für das große Ganze (unendlich lange Spiele) ist die Antwort noch offen, aber für den Anfang ist der Trick nach rechts die beste Wahl, die man haben kann!

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des Papers „Experimenting with Permutation Wordle" von Aurora Hiveley auf Deutsch:

1. Problemstellung

Das Paper untersucht das Spiel „Permutation Wordle", eine Variante des bekannten Wort-Rätsels „Wordle", entwickelt von Samuel Kutin und Lawren Smithline.

• Spielmechanik: Ein Spielleiter wählt eine geheime Permutation $\sigma$ der Menge $\{1, \dots, n\}$ aus. Ein Spieler versucht, diese Permutation durch Raten zu erraten.
• Feedback: Nach jedem Raten (einer Permutation $\gamma$) erhält der Spieler die Information, welche Indizes korrekt sind (d. h. $\gamma[i] = \sigma[i]$).
• Ziel: Die geheime Permutation in möglichst wenigen Raten zu finden.
• Die Vermutung: Kutin und Smithline schlagen eine Strategie namens „Cyclic Shift" (CS) vor. Dabei werden alle falsch platzierten Elemente in der nächsten Runde um eine Position nach rechts verschoben, während korrekt platzierte Elemente fixiert bleiben. Sie vermuten, dass diese Strategie optimal ist, definiert als die Strategie, die die Wahrscheinlichkeit des Erfolgs innerhalb von $r$ Raten maximiert (bzw. die durchschnittliche Anzahl der benötigten Raten minimiert).

2. Methodik

Die Autorin verwendet einen hybriden Ansatz aus experimenteller Datenanalyse und mathematischer Beweisführung, um die Vermutung zu untersuchen.

• Formalisierung der Strategie: Eine Strategie $S$ wird als Vektor $[s_1, s_2, \dots, s_n]$ definiert, wobei $s_i$ eine Permutation der Länge $i$ ist. Um den nächsten Raten $\gamma_{r+1}$ aus dem aktuellen $\gamma_r$ zu generieren, werden die korrekten Positionen ($J_r$) fixiert und die falschen Positionen ($I_r$) gemäß der Komponente $S[|I_r|]$ permutiert.
• Einschränkung auf Derangement und Zyklische Permutationen:
  • Es wird angenommen, dass Strategie-Komponenten Derangements (Permutationen ohne Fixpunkte) sein müssen, um ineffiziente Zyklen zu vermeiden.
  • Zur Vereinfachung der Berechnung und Vermeidung von Endlosschleifen konzentriert sich der Großteil der Analyse auf zyklische Permutationen als Strategie-Komponenten.
• Experimentelle Analyse: Mit Hilfe des Computer-Algebra-Systems Maple wurden Strategien für $n$ bis zu 8 (für induktive Strategien) und $n$ bis zu 5 (für allgemeine Derangement-Strategien) simuliert. Die durchschnittliche Anzahl der Raten wurde über alle $n!$ möglichen geheimen Permutationen gemittelt.
• Erzeugende Funktionen (Generating Functions): Der Kern der mathematischen Analyse basiert auf der Erzeugenden Funktion $f_S(x)$ einer Strategie $S$. Der Koeffizient $a_r = [x^r]f_S(x)$ gibt an, wie viele Permutationen der Länge $n$ mit dieser Strategie exakt in $r$ Raten gelöst werden können.
  • Die Optimalität wird durch den Vergleich der Koeffizienten für $r=1, 2, 3$ untersucht.

3. Wichtige Beiträge und Ergebnisse

A. Induktive Konstruktion und erste Raten

• Raten 1 und 2: Es wird bewiesen (Theorem 4.1), dass für jede Strategie $S$ der Koeffizient für 1 Rate immer 1 ist (nur die triviale Permutation) und der Koeffizient für 2 Raten immer der Euler-Zahl $A(n, 1)$ entspricht. Dies liegt daran, dass die ersten beiden Raten bei nicht-derangierten Permutationen durch die unteren Indizes der Strategie bestimmt werden, die bei induktiven Strategien identisch sind.
• Erwartungswert: Es wird gezeigt, dass alle Derangement-Strategienkomponenten $S[n]$ im Durchschnitt die gleiche Anzahl korrekter Indizes nach dem ersten Rate-Schritt liefern (Proposition 3.1). Daher muss die Optimalität in den späteren Schritten des Spiels liegen.

B. Analyse der dritten Rate (Kubische Koeffizienten)

Der Hauptbeitrag des Papers ist der Beweis der Optimalität von „Cyclic Shift" (CS) für Spiele, die in genau drei Raten enden.

• Theorem 4.3 & 4.8: Für induktive Strategien $S$ (die CS für alle $i < n$ verwenden, aber $S[n]$ variieren) wird gezeigt, dass die Anzahl der Permutationen, die in genau 3 Raten gelöst werden können, für CS maximal ist.

  • Der Beweis zerlegt die Fälle basierend auf dem ersten Rate, bei dem ein korrektes Element gefunden wird ($\rho_S(\pi) = i$).
  • Für $i=1$ und $i=3$ sind die Anzahlen unabhängig von der spezifischen Wahl von $S[n]$.
  • Der entscheidende Unterschied liegt im Fall $\rho_S(\pi) = 2$ (kein Treffer im ersten, Treffer im zweiten Rate).
  • Ergebnis: Die Anzahl der zulässigen Mengen korrekter Indizes im zweiten Rate ist für die Standard-Right-Shift-Strategie (CS) strikt größer als für jede andere induktive Strategie. Dies führt zu $[x^3]f_{CS}(x) > [x^3]f_S(x)$.

• Worst-Case-Analyse (Theorem 4.9 & 4.11):

  • Die am wenigsten effiziente Strategie unter den induktiven Varianten ist die CSL (Cyclic Shift Left), die links verschoben wird, aber induktiv rechts verschoben für kleinere Teilmengen.
  • Die Anzahl der in 3 Raten lösbaren Permutationen für CSL wird durch die Lucas-Zahlen ($L_n$) ausgedrückt: $| \{ \pi \mid \rho_{CSL}(\pi) = 2 \} | = L_n - n - 1$.
  • Es wird bewiesen, dass jede andere induktive Strategie mehr Permutationen in 3 Raten lösen kann als CSL.

C. Experimentelle Bestätigung

Die Maple-Simulationen bestätigten die Vermutung von Kutin-Smithline für:

• Zyklische Strategien bis $n=7$.
• Allgemeine Derangement-Strategien bis $n=5$.
• Induktiv konstruierte Strategien bis $n=8$.

4. Signifikanz und Fazit

• Beweis für $r=3$: Das Paper liefert einen rigorosen mathematischen Beweis, dass die „Cyclic Shift"-Strategie optimal ist für Spiele, die in genau drei Raten enden. Dies ist ein signifikanter Schritt zur Validierung der allgemeinen Vermutung.
• Methodischer Fortschritt: Die Anwendung von Erzeugendenfunktionen und die Zerlegung nach dem ersten Treffer ($\rho_S(\pi)$) bietet ein neues Werkzeug zur Analyse von Permutations-Rätseln.
• Einschränkungen und Ausblick:
  • Die Ergebnisse gelten derzeit nur für Spiele, die in 1, 2 oder 3 Raten enden. Die Analyse höherer Koeffizienten ($r \ge 4$) ist komplexer und wurde nicht vollständig bewiesen.
  • Die Analyse beschränkte sich stark auf zyklische Permutationen und induktive Strategien. Eine Verallgemeinerung auf beliebige Derangements oder nicht-induktive Strategien (die sich mitten im Spiel ändern) bleibt offen.
  • Die Arbeit legt nahe, dass für $r \ge 4$ nuanciertere Ansätze erforderlich sein könnten, da die experimentellen Muster für höhere Koeffizienten weniger eindeutig sind.

Zusammenfassend stützt das Paper die Hypothese, dass „Cyclic Shift" die optimale Strategie für Permutation Wordle ist, und liefert den ersten formalen Beweis für den Fall der dreischrittigen Spiele, während es gleichzeitig die Grenzen der aktuellen Methoden aufzeigt.