On an Erdős-Szekeres Game

Dit artikel onderzoekt een tweespeler-permutatiespel geïnspireerd op de beroemde stelling van Erdős-Szekeres en bepaalt de winnaar en een winnende strategie voor het geval dat $a \geq b$ en $b \in \{2,3,4,5\}$.

De kern

Het Grote Getallen-Gokspel: Een Strijd om de Langste Rij

Stel je voor dat je een spelletje speelt met een vriend. Jullie hebben een grote doos met genummerde balletjes (1, 2, 3, etc.). Jullie trekken om de beurt een balletje en leggen het op een rijtje.

Het doel van het spel is eigenlijk een valstrik: Wie de eerste is die een te lange rijtje maakt, verliest.

• Als je een rijtje maakt dat steeds groter wordt (bijv. 2, 5, 8, 12), en dat rijtje wordt te lang, dan heb je verloren.
• Als je een rijtje maakt dat steeds kleiner wordt (bijv. 10, 7, 3, 1), en dat wordt ook te lang, dan ben je ook de dupe.

Dit spel is gebaseerd op een beroemde wiskundige regel uit 1935 (de stelling van Erdős en Szekeres). Die regel zegt eigenlijk: "Als je maar lang genoeg doorgaat met trekken, kun je niet voorkomen dat je op een gegeven moment een te lange stijgende of dalende rij maakt."

De auteur van dit paper, Lara Pudwell, heeft een manier bedacht om te winnen in dit spel, zolang je maar slim speelt. Ze noemt dit een "Misère"-spel: wie de laatste zet doet die de valstrik activeert, verliest.

De Magische Landkaart (Het Bord)

In plaats van te denken aan getallenrijen, tekent de auteur een landkaart (een rooster) om het spel te visualiseren. Dit is de kern van haar ontdekking.

• Het Rooster: Stel je een rechthoekig veld voor, net als een bord met vakjes.
• De Spelers: Elke keer als een speler een getal kiest, "verft" hij of zij een vakje op dit bord in.
• De Regel: Je mag alleen vakjes verven die direct naast een al ingekleurd gebied liggen. Je kunt niet zomaar een vakje in het midden kiezen.
• De Valstrik: Het spel eindigt als het hele bord vol is. De speler die het laatste hoekje (rechtsonder) moet verven, heeft het bord volgekleurd. Dat betekent dat de tegenstander nu geen zet meer kan doen zonder een te lange rij te maken. Dus: Wie het laatste hoekje claimt, wint.

Het is alsof je een muur aan het bouwen bent. Jullie bouwen om de beurt een baksteen. Wie de laatste baksteen moet leggen om de muur dicht te maken, heeft de tegenstander in de val gelokt.

De Strategieën: Hoe win je?

De auteur heeft voor verschillende moeilijkheidsgraden (hoe lang de verboden rij mag zijn) een winnende strategie bedacht.

1. Het Eenvoudige Spel (b = 2)

Stel, je mag geen rijtje van 2 dalende getallen maken.

• De strategie: Het bord is nu heel smal (één rij). De spelers moeten simpelweg van links naar rechts vullen.
• Wie wint? Dit hangt af van of het totale aantal vakjes even of oneven is. Het is als het vullen van een rij stoelen; wie op de laatste stoel moet zitten, verliest.

2. Het Twee-Rijen Spel (b = 3)

Nu mag je geen rijtje van 3 dalende getallen maken. Het bord heeft twee rijen.

• De strategie: Speler 1 (de eerste die begint) kan altijd winnen.
• De analogie: Stel je voor dat je een trap beklimt. Als de tegenstander een stap naar boven zet, zet jij een stap naar voren. Als hij naar voren zet, zet jij naar boven. Jij houdt het evenwicht zo dat jij altijd de controle hebt over de laatste stap. Je "mirreert" de tegenstander op een slimme manier.

3. Het Drie-Rijen Spel (b = 4)

Nu mag je geen rijtje van 4 dalende getallen maken. Het bord heeft drie rijen.

• De strategie: Dit wordt iets ingewikkelder, maar Speler 1 heeft nog steeds een winnende strategie.
• De analogie: Het is alsof je een labyrint doorloopt. De auteur laat zien dat Speler 1 altijd een pad kan kiezen dat de tegenstander in een hoek drijft. Hoe dan ook de tegenstander ook probeert te ontsnappen, Speler 1 kan de uitgang blokkeren.

4. Het Vier-Rijen Spel (b = 5) – De Grote Uitdaging

Dit is het meest complexe deel van het paper. Nu mag je geen rijtje van 5 dalende getallen maken.

• De strategie: Hier heeft de auteur een nieuwe strategie bedacht die nog nooit eerder zo duidelijk is beschreven.
• Hoe werkt het? Ze heeft een computer gebruikt om miljoenen mogelijke spellen te simuleren. Ze ontdekte dat er bepaalde "veilige zones" zijn op het bord.
  • Stel je voor dat je een danspartner hebt. Je probeert altijd in een specifieke dansstijl te blijven (de "veilige zone").
  • Wat je partner ook doet (een stap links, rechts, vooruit), jij hebt een antwoord dat jullie weer terugbrengt naar die veilige zone.
  • Uiteindelijk loop je je partner vast in een hoek waar hij/zij geen keuze meer heeft dan de valstrik te activeren.

Waarom is dit belangrijk?

Voorheen wisten wiskundigen dat je dit spel op een computer kon oplossen voor kleine getallen, maar ze dachten dat het te moeilijk was om een algemene regel te vinden voor grotere getallen.

Dit paper laat zien dat:

1. Je dit spel kunt zien als het invullen van een rooster (in plaats van getallen).
2. Er voor bepaalde scenario's (tot en met 5) een vaste winnende strategie is voor de eerste speler.
3. De strategie voor het moeilijke geval (b=5) een nieuwe manier biedt om naar dit probleem te kijken, zelfs als het een beetje ingewikkeld is om uit te leggen.

Samenvatting in één zin

Dit paper is een handleiding voor het winnen van een wiskundig spelletje waarbij je probeert te voorkomen dat je een te lange rij maakt, door het spel te vertalen naar het slim invullen van vakjes op een bord, waarbij de eerste speler bijna altijd een winnende route kan vinden.

Het is als een schaakpartij waarbij de eerste speler een plan heeft dat de tegenstander, hoe slim hij ook is, altijd in de val laat lopen.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "On an Erdős-Szekeres Game" van Lara Pudwell, geschreven in het Nederlands.

Titel: Over een Erdős-Szekeres Spel

Auteur: Lara Pudwell (Valparaiso University, USA)
Publicatie: Discrete Mathematics and Theoretical Computer Science, Vol. 27:1, Permutation Patterns 2024 #6 (2026).

---

1. Probleemstelling

Het artikel onderzoekt een tweespelersgame die is gebaseerd op het beroemde Erdős-Szekeres-stelling (1935). Deze stelling stelt dat elke permutatie van lengte $n \ge (a-1)(b-1)+1$ ofwel een stijgende deelrij van lengte $a$ ($I_a$) ofwel een dalende deelrij van lengte $b$ ($J_b$) bevat.

De game wordt als volgt gespeeld:

• Twee spelers kiezen om de beurt getallen uit de verzameling $\{1, 2, \dots, n\}$ om een permutatie te construeren.
• De game eindigt zodra een speler een $I_a$-patroon of een $J_b$-patroon voltooit.
• De focus ligt op de misère-versie van de game: de speler die het patroon voltooit, verliest. (Dit staat in contrast met de "normale" play waarbij de eerste die het patroon maakt wint).
• De parameters zijn positieve gehele getallen $a$ en $b$ met $a \ge b$.

Het doel is om de winnende speler te bepalen en een winnende strategie te formuleren voor specifieke waarden van $b$ (namelijk $b \in \{2, 3, 4, 5\}$) en willekeurige $a \ge b$.

2. Methodologie: Grid-Shading Model

De kern van de methodologie is een visuele vertaling van de permutatiegame naar een 2D-rooster (grid), geïnspireerd door het bewijs van Seidenberg (1959) van de stelling van Erdős-Szekeres.

• Het Bord: Het spel wordt gemodelleerd als een rooster van $(b-1)$ rijen en $(a-1)$ kolommen.
• Cellen: Elke cel $(c, r)$ vertegenwoordigt een toestand waarbij de langste stijgende deelrij eindigend op het huidige getal lengte $c$ heeft, en de langste dalende deelrij lengte $r$ heeft.
• Gekleurde Cellen: Een speler "kleurt" (shade) een cel $(c, r)$ wanneer een nieuw getal in de permutatie wordt toegevoegd dat deze specifieke lengtes van stijgende en dalende deelrijen oplevert.
• Geëlimineerde Regio: Als een cel $(c, r)$ is gekleurd, worden alle cellen $(c', r')$ met $c' \le c$ en $r' \le r$ "geëlimineerd" (ongeldig voor toekomstige zetten). Dit creëert een continue, samenhangende regio van geëlimineerde cellen.
• Spelregels op het Bord:
  1. Speler 1 begint met het kleuren van de linkerbovenhoek $(1,1)$.
  2. Spelers kleuren om de beurt een cel die rand-aangrenzend is aan de bestaande geëlimineerde regio.
  3. De speler die de rechtsonderhoek $(a-1, b-1)$ claimt, wint (in de misère-versie), omdat dit betekent dat de volgende speler gedwongen is een patroon te voltooien.
• Vergelijking met eerdere werken: Dit model is een visuele variant van het "ternary word"-model dat eerder werd gebruikt door Albert et al. (2009). Het roostermodel maakt het makkelijker om geometrische patronen en strategieën visueel te analyseren.

3. Belangrijkste Bijdragen en Resultaten

De auteur levert winnende strategieën voor Speler 1 (de eerste speler) voor de misère-game onder de voorwaarde $a \ge b$ voor de volgende gevallen:

Geval $b=2$

• Het bord is een 1-rige rij van $(a-1)$ kolommen.
• Resultaat: De winnaar hangt af van de pariteit van $a$.
  • Als $a$ even is, wint Speler 1.
  • Als $a$ oneven is, wint Speler 2.
• Dit komt omdat spelers gedwongen zijn de linkermogelijkste beschikbare cel te kleuren.

Geval $b=3$

• Het bord is een $2 \times (a-1)$ rooster.
• Resultaat: Speler 1 heeft een winnende strategie voor alle $a \ge 3$.
• Strategie: Speler 1 handhaaft een specifieke configuratie waarbij rij 1 en rij 2 een afwisselend patroon van gekleurde cellen hebben. Speler 1 kan altijd reageren op de zet van Speler 2 om de balans te behouden, waardoor Speler 2 uiteindelijk de hoekcel moet nemen.

Geval $b=4$

• Het bord is een $3 \times (a-1)$ rooster.
• Resultaat: Speler 1 heeft een winnende strategie voor alle $a \ge 4$.
• Strategie: De strategie wordt beschreven in termen van het behouden van twee specifieke board-vormen (klassen van geëlimineerde cellen) na elke beurt van Speler 1. Ongeacht wat Speler 2 doet, kan Speler 1 terugkeren naar een van deze twee vormen, wat uiteindelijk leidt tot een winnende eindfase.

Geval $b=5$ (Nieuwe Bijdrage)

• Het bord is een $4 \times (a-1)$ rooster.
• Resultaat: Speler 1 heeft een winnende strategie voor alle $a \ge 5$.
• Methodologie: Dit is de meest complexe case. De strategie is ontwikkeld via een computer-ondersteunde zoektocht naar winnende posities (klasse N) en verliezende posities (klasse P).
• De Strategie: De auteur definieert een verzameling van zeven specifieke board-toestanden genaamd $\mathcal{S}$.
  • Speler 1 probeert na elke beurt de board in een staat uit $\mathcal{S}$ te houden.
  • Een uitgebreide casestudie (gebaseerd op computerdata) toont aan dat ongeacht de zet van Speler 2, Speler 1 altijd kan reageren om terug te keren naar een staat in $\mathcal{S}$.
  • Uiteindelijk kan Speler 1 de game sturen naar een "eindspel"-verzameling $\mathcal{E}$, waar een "tit-for-tat" strategie garandeert dat Speler 2 de laatste zet moet doen.
• Dit resultaat gaat verder dan wat eerder bekend was in de literatuur (Albert et al.), die zich voornamelijk richtte op de normale play-versie of beperkte strategieën voor misère play.

4. Significatie en Discussie

• Visuele Intuïtie: Het roostermodel biedt een krachtig alternatief voor de eerder gebruikte taaltheoretische benadering (ternary words), waardoor geometrische patronen in de speltoestanden direct zichtbaar worden.
• Uitbreiding van Bestaande Kennis: Hoewel Albert et al. (2009) al strategieën hadden voor $b \le 5$ in de normale play-versie, waren de strategieën voor de misère-versie (waarbij de maker van het patroon verliest) minder volledig uitgewerkt, vooral voor $b=5$. Dit artikel vult dat gat.
• Complexiteit: De auteur merkt op dat de strategie voor $b=5$ aanzienlijk complexer is dan voor kleinere $b$, en dat de huidige methodologie (handmatige analyse van computerdata) moeilijk schaalbaar is voor grotere $b$. Er is een conjectuur dat Speler 1 ook wint voor $b \ge 6$ in de normale play-versie, maar een expliciete strategie voor misère play met grote $b$ blijft een uitdaging.
• Aantal Zetten: Het artikel analyseert ook het aantal zetten dat nodig is. Terwijl de theoretische bovengrens $(a-1)(b-1)+1$ is, gebruiken de geoptimaliseerde strategieën vaak minder zetten (bijvoorbeeld ongeveer $2a$voor$b=3$en$4$).
• Toekomstig Onderzoek: Er worden vragen gesteld over de convergentie van het percentage verliezende posities (klasse P) naarmate $a$ toeneemt en of er efficiëntere strategieën bestaan voor $b=5$.

Conclusie

Lara Pudwell presenteert een volledig geanalyseerde oplossing voor de misère-versie van het Erdős-Szekeres spel voor $b \in \{2, 3, 4, 5\}$. Door een visueel roostermodel te combineren met computer-ondersteunde zoektochten, wordt bewezen dat Speler 1 een winnende strategie heeft voor alle $a \ge b$ in deze gevallen. Dit werk verrijkt het begrip van combinatorische spellen op permutaties en biedt een nieuwe, visuele framework voor toekomstig onderzoek op dit gebied.