Additive Subtraction Games

Dit artikel levert een volledig bewijs voor de volledige nim-waarde-structuur van additieve aftrekspellen in het primitief kwadratische regime, door te aantonen dat elke nim-waardeserie ligt op een lineaire verschuiving van de klassieke P-posities die worden beschreven door een gesloten formule met Beatty-achtige uitdrukkingen.

De kern

Stel je voor dat je een spelletje speelt met stapels munten. Twee spelers wisselen elkaar af om munten van de stapel te nemen. Maar er is een regel: je mag alleen een bepaald aantal munten wegnemen, bijvoorbeeld 3, 5 of 8. Als je geen enkele zet meer kunt doen omdat je minder munten hebt dan het kleinste aantal dat je mag nemen, dan heb je verloren.

Dit klinkt als een simpel kinderspel, maar wiskundigen noemen dit een "aftrekspel" (subtraction game). De grote vraag is: wie wint er als je perfect speelt?

Deze paper van Urban Larsson en Hikaru Manabe lost precies dit probleem op voor een heel specifieke, maar complexe versie van zo'n spel. Hier is de uitleg in gewone taal, met een paar creatieve vergelijkingen.

1. Het Spel en de "Magische Formule"

In dit specifieke spel mag je munten wegnemen in groepjes van:

• $a$ munten
• $b$ munten
• $a + b$ munten

De auteurs kijken naar een situatie waarbij $a$ en $b$ een specifieke verhouding hebben (de "primitieve kwadratische regime"). Dit is als het ware het "gouden midden" van de complexiteit: niet te simpel, maar ook niet volledig chaotisch.

Sinds 1982 weten wiskundigen dat er een magische formule bestaat om te voorspellen welke stapelgroottes een "verliespositie" zijn (in het vakjargon: P-posities). Als je op zo'n positie staat, verlies je als de tegenstander perfect speelt. De formule ziet eruit als een ingewikkelde mix van getallen en vloerfuncties (zoals $\lfloor n/a \rfloor$).

Het probleem: Iedereen dacht dat deze formule klopte, maar niemand had ooit een echt, waterdicht bewijs geleverd. Het was als een recept voor een taart dat iedereen gebruikte, maar waar niemand de exacte chemie achter had uitgelegd.

2. De Oplossing: De "Ladder" van de Winnaar

De auteurs hebben nu eindelijk het bewijs geleverd. Ze laten zien dat de winnende strategie niet willekeurig is, maar volgt een heel strak patroon.

Stel je voor dat de mogelijke stapelgroottes (0, 1, 2, 3...) een lange ladder zijn. De auteurs ontdekken dat deze ladder in vier verschillende soorten treden is verdeeld, elk met een eigen kleur:

1. De Groene Treden (Waarde 0): Dit zijn de verliesposities. Als je hier staat, ben je in de problemen. De auteurs bewijzen dat deze treden precies worden gevormd door die magische formule.
2. De Blauwe Treden (Waarde 1): Als je hier staat, kun je met één zet naar een Groene trede springen. Je wint dus.
3. De Gele Treden (Waarde 2): Ook hier kun je naar een Groene trede springen, maar dan via een iets andere route.
4. De Rode Treden (Waarde 3): Dit is het meest interessante deel. Hier kun je ook naar een Groene trede springen, maar er is een kleine "valstrik" in de formule die ervoor zorgt dat deze treden net anders liggen dan de andere.

De paper laat zien dat deze vier kleuren samen de hele ladder bedekken. Er is geen enkele stapelgrootte die niet in één van deze vier categorieën past. Het is alsof ze de hele ladder hebben ingekleurd zonder een gat te laten.

3. De "Botst" (Collision) en de Wiskundige Puzzel

Het moeilijkste deel van hun werk was het bewijzen van de Rode Treden (waarde 3).

Om dit te doen, moesten ze een heel specifiek wiskundig fenomeen analyseren: Botstingen.
Stel je voor dat je de Groene treden (de verliesposities) op een lijn tekent. Als je nu een stukje van de lijn afsnijdt en dat stukje verschuift (bijvoorbeeld 7 stappen naar links), vallen sommige van die verschoven treden dan precies op de originele Groene treden?

• Als dat gebeurt, is er een "botsing".
• De auteurs moesten precies tellen hoeveel van deze botsingen er in één cyclus voorkomen.

Ze ontdekten dat deze botsingen niet willekeurig gebeuren. Ze volgen een ritme dat afhangt van de restantjes als je de getallen deelt door $a$ en $\delta$. Ze deelden de getallen in drie gebieden in:

• Links-beperkt: Hier zijn de botsingen beperkt door de linkerkant.
• Onbeperkt: Hier kunnen ze vrij gebeuren.
• Rechts-beperkt: Hier zijn ze beperkt door de rechterkant.

Door dit ritme te begrijpen, konden ze bewijzen dat het aantal Rode treden precies klopt met wat nodig is om de hele ladder te vullen. Het is als het oplossen van een legpuzzel waarbij je eerst moet bewijzen dat het aantal stukjes in de hoek precies klopt voordat je de rest kunt leggen.

4. Waarom is dit belangrijk?

Voor de gemiddelde speler is dit misschien alleen maar een leuk weetje. Maar voor wiskundigen is dit een grote stap.

• Het bewijs: Ze hebben een 40 jaar oud raadsel opgelost dat in het beroemde boek Winning Ways stond.
• De structuur: Ze tonen aan dat zelfs in complexe spellen, waar getallen op een ingewikkelde manier met elkaar verweven zijn, er een onderliggende orde zit. Het is alsof ze een verborgen symfonie hebben gevonden in een ogenschijnlijk luidruchtig orkest.
• Toekomst: Hun methode (het tellen van botsingen in een "bracket expression") kan misschien helpen om andere, nog complexere spellen op te lossen.

Samenvatting in één zin

De auteurs hebben bewezen dat bij een specifiek, complex muntenspel, de winnende en verliezende posities niet willekeurig zijn, maar volgen een strak, vierkleurig patroon dat wordt bepaald door een elegante wiskundige formule, en ze hebben eindelijk het bewijs geleverd waarom die formule werkt.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Additive Subtraction Games" van Urban Larsson en Hikaru Manabe, geschreven in het Nederlands.

Titel: Additieve Subtraktiespellen: De Nim-waarde Structuur in het Primitieve Kwantadische Regime

1. Probleemstelling

Het artikel onderzoekt de nim-waarden (ook wel nimbers genoemd) van een specifiek type tweespelersspel, genaamd additieve subtraktiespellen.

• Het spel: Spelers nemen beurtelings een aantal counters (stenen) uit een hoop. De toegestane aantallen om te verwijderen zijn vastgelegd in de verzameling $S = \{a, b, a+b\}$, waarbij $b = a + \delta$.
• De context: Dit probleem werd oorspronkelijk geïntroduceerd in het klassieke werk Winning Ways (Berlekamp et al., 1982). Hoewel er een gesloten formule bestaat voor de $P$-posities (verliezende posities, met nim-waarde 0) in een specifiek parameterbereik, ontbrak er tot nu toe een volledig wiskundig bewijs in de literatuur.
• Het focusgebied: De auteurs concentreren zich op het primitieve kwadratische regime, gedefinieerd door de voorwaarden:
  • $a < \delta < 2a$
  • $\gcd(a, \delta) = 1$
  • $b = a + \delta$
    In dit regime interageren de schalen $a$ en $\delta$ op een niet-triviale manier, wat leidt tot kwadratische complexiteit in de structuur van het spel.

2. Methodologie

De auteurs combineren combinatorische speltheorie met elementaire getaltheorie om de volledige structuur van de nim-waarden te onthullen.

• De Kandidaat $P$-posities: Ze beginnen met een bestaande gesloten formule voor de $P$-posities ($W_0$), uitgedrukt als een "klokbewerking" (bracket expression) op rationale modulussen:
  $$w_n = n + a \left\lfloor \frac{n}{a} \right\rfloor + b \left\lfloor \frac{n}{\delta} \right\rfloor$$
  De verzameling $W_0 = \{w_n : n \ge 0\}$ wordt geïdentificeerd als de verzameling van posities met nim-waarde 0.

• Inductief Bewijs (Mex-regel): De kern van de bewijsvoering is een sterke inductie over de grootte van de hoop. Ze verifiëren de mex-regel (minimale excluderende waarde):

  1. Anti-collisie: Geen enkele verplaatsing (subtraktie met $a, b,$ of $a+b$) kan leiden van de ene $P$-positie naar een andere.
  2. Bereikbaarheid: Van elke positie met een hogere nim-waarde moet er een verplaatsing mogelijk zijn naar een positie met een lagere nim-waarde.

• Getaltheoretische Analyse: Om de bereikbaarheid en de verdeling van de andere nim-waarden (1, 2 en 3) te bewijzen, analyseren de auteurs de gaten (gaps) tussen opeenvolgende $P$-posities. Ze introduceren het concept van $\delta$-collisies: het tellen van paren $(m, n)$ waarbij $w_n - w_m = \delta$. Dit is cruciaal voor het bepalen van de grootte van de verzameling met nim-waarde 3.

3. Belangrijkste Bijdragen en Resultaten

A. Volledige Classificatie van Nim-waarden (Hoofdstelling)
De auteurs bewijzen dat de natuurlijke getallen $\mathbb{N}_0$ worden gepartitioneerd in precies vier disjuncte verzamelingen, elk corresponderend met een unieke nim-waarde:

1. Nim-waarde 0 ($W_0$): De verzameling $P$-posities, gegeven door de gesloten formule $w_n$.
2. Nim-waarde 1 ($W_1$): De verzameling $W_0 + a$ (elk element van $W_0$ verschoven met $a$).
3. Nim-waarde 2 ($W_2$): De verzameling $W_0 - b$ (verschoven met $-b$).
4. Nim-waarde 3 ($W_3$): De verzameling $(W_0 - \delta) \setminus W_0$. Dit zijn de posities die een verschuiving van $\delta$ van een $P$-positie zijn, maar zelf geen $P$-positie zijn.

B. De Periodiciteit en Structuur

• De auteurs tonen aan dat de reeks van $P$-posities een index-periode heeft van $a\delta$.
• De hoop-periode (de lengte van de cyclus van de spelposities zelf) is $(3\delta + a)a$.
• De gaten tussen opeenvolgende $P$-posities nemen slechts vier waarden aan: $\{1, a+1, b+1, a+b+1\}$. De locatie van deze gaten wordt bepaald door de restklassen van de index modulo $a$ en $\delta$.

C. De $\delta$-Collisie Telling (Kernresultaat)
Een van de meest technische en belangrijke resultaten is het tellen van het aantal $\delta$-collisies binnen één periode.

• Ze definiëren de verzameling $C = (W_0 - \delta) \cap W_0$.
• Ze bewijzen dat het aantal elementen in $C$ binnen één hoop-periode gelijk is aan $a \cdot d$, waarbij $d = \delta - a$.
• Dit resultaat wordt afgeleid door de analyse van "collisiefensters" rondom de gaten van grootte $a+1$. Ze tonen aan dat de verdeling van deze collisies afhankelijk is van drie residu-regio's (links-beperkt, onbeperkt, rechts-beperkt) die worden bepaald door de relatie tussen $a$ en $\delta$.

D. Bevestiging van de Partitie
Door het aantal elementen in elke van de vier verzamelingen ($W_0, W_1, W_2, W_3$) binnen één periode op te tellen, tonen ze aan dat de som exact gelijk is aan de totale hoop-periode. Dit bewijst dat er geen posities overblijven en dat de classificatie compleet is.

4. Significatie en Impact

• Oplossing van een oud probleem: Het artikel levert het eerste volledige bewijs voor de gesloten formule van de $P$-posities in het primitieve kwadratische regime, een stelling die al decennialang in Winning Ways stond zonder bewijs.
• Verduidelijking van Complexiteit: Het werk bevestigt dat het primitieve kwadratische regime ($a < \delta < 2a$) de bron is van de kwadratische complexiteit in dit type spellen. Buiten dit regime reduceert het probleem tot lineaire complexiteit of behoudt het een eenvoudiger structuur.
• Verbinding met Getaltheorie: Het artikel introduceert een nieuwe manier om "klokbewerkingen" (bracket expressions) te analyseren door middel van het tellen van collisies bij verschuivingen. Dit biedt inzicht in de meetkunde van gaten in sequenties die worden gegenereerd door vloerfuncties.
• Toekomstige Richtingen: De auteurs formuleren open vragen over het uitbreiden van deze methode naar spellen met meer termen in de subtraktie-verzameling en het bestuderen van de "shift-collision structuur" voor algemene verschuivingen $k$, wat een brug slaat tussen combinatorische speltheorie en de theorie van Beatty-rijen en Fraenkel's conjectuur.

Conclusie:
Larsson en Manabe hebben een diepgaande, getaltheoretische oplossing gevonden voor een klassiek speltheoretisch probleem. Ze hebben niet alleen de $P$-posities bewezen, maar ook de volledige nim-waarde structuur (0, 1, 2, 3) afgeleid en bewezen dat deze de gehele ruimte van spelposities in het kwadratische regime volledig en correct dekt.