The Nim-Sum of a Random Integer Partition

Stel je een spel voor dat wordt gespeeld met stapels stenen, waarbij twee spelers om de beurt een willekeurig aantal stenen uit een enkele stapel mogen halen. Het doel is om de laatste te zijn die een zet doet, of om de tegenstander omgekeerd in een positie te dwingen waarin deze geen winnende zet meer heeft. Dit is het spel Nim, een klassiek strategisch raadsel dat al meer dan een eeuw wordt bestudeerd. Het geheim van winnen ligt niet in het tellen van het totaal aantal stenen, maar in een specifieke manier om de groottes van de stapels te combineren met behulp van een regel die optellen en aftrekken mengt op een binaire wijze. Als deze combinatie nul oplevert, is de speler die aan de beurt is om te bewegen gedoemd te verliezen, ervan uitgaande dat de tegenstander perfect speelt. Decennialang hebben wiskundigen geweten hoe ze deze verliezende posities voor elke specifieke schikking van stapels kunnen identificeren, maar een diepere, meer ongrijpbare vraag bleef over: als je simpelweg een vast aantal stenen verzamelt en ze willekeurig in stapels verdeelt, hoe vaak zal zo'n willekeurige schikking dan een verliezende een zijn?

Deze vraag bevindt zich op het snijvlak van speltheorie en de studie van de partiëntenleer, het wiskundige veld dat zich bezighoudt met hoe een getal kan worden afgebroken in kleinere gehele getallen. Hoewel de regels voor het spelen van een enkel spel precies en deterministisch zijn, is het gedrag van deze spellen wanneer de beginpositie willekeurig wordt gekozen verrassend complex. Een natuurlijke vraag is of de frequentie van verliezende posities een eenvoudig asymptotisch patroon volgt naarmate het totaal aantal stenen groeit. Echter, het nieuwe werk van Daewon Kim van de University of Hawai'i at Mānoa onthult dat het antwoord veel ingewikkelder is dan een eenvoudige stabilisatie. Hoewel de kans op een verliezende positie zelf steeds kleiner wordt naarmate het aantal stenen groeit, stabiliseert de relatieve dichtheid van deze posities niet. In plaats van glad te strijken tot een constant gemiddelde, oscilleert de genormaliseerde dichtheid in een grillig, herhalend patroon dat nooit echt stabiliseert, ongeacht hoe groot het aantal stenen ook wordt.

Kim's onderzoek richt zich op het specifieke geval waarbij het totaal aantal stenen even is, aangezien de regels van het spel het onmogelijk maken voor een oneven totaal om ooit een verliezende positie te vormen. Door middel van exacte berekeningen bepaalt de studie hoe de waarschijnlijkheid van een verliezende positie zich gedraagt naarmate het totaal aantal stenen toeneemt. De bevindingen tonen aan dat de ruwe waarschijnlijkheid naar nul nadert, maar de genormaliseerde waarde, die de kans corrigeert voor de natuurlijke afname, niet naar een enkele constante waarde convergeert. In plaats daarvan fluctueert deze wild in een zaagtandpatroon dat zich herhaalt telkens wanneer de natuurlijke schaal die bij de grootte van de stapel hoort een macht van twee kruist. Als je de genormaliseerde waarschijnlijkheid uitzet tegen de grootte van de stapel, zou je een lijn zien die gestaag klimt van een laag punt naar een hoog punt, dan scherp terugvalt, om vervolgens weer te beginnen met klimmen. Deze cyclus herhaalt zich oneindig, wat betekent dat de genormaliseerde waarde ergens tussen één en twee keer een specifieke basiswaarde kan liggen, afhankelijk van waar je je in deze cyclus bevindt.

Het mechanisme dat dit gedrag aandrijft, is geworteld in de binaire aard van de winregel van het spel. Wanneer een groot getal wordt afgebroken in kleinere delen, fungeren de kleinste delen als een bron van willekeur die de lagere bits van de binaire getallen door elkaar husselt, waardoor ze uniform en onvoorspelbaar lijken. De grootste delen zijn zo zeldzaam dat ze zelden invloed hebben op de uitkomst. Er is echter een specifieke middelste reeks van deelgroottes die fungeert als een kritieke flessenhals. In deze reeks zijn de delen groot genoeg om betekenisvol te zijn, maar niet zo groot dat ze verdwijnen. Het aantal delen dat in deze specifieke reeks valt, bepaalt de uitkomst. Omdat deze reeks verschuift naarmate het totaal aantal stenen groeit, slaat de balans van het spel heen en weer. Wanneer de natuurlijke schaal net onder een macht van twee ligt, neigt de balans de ene kant op; wanneer deze drempel wordt gekruist, slaat de balans om, waardoor de waarschijnlijkheid springt.

Om dit te begrijpen, kan men het proces vergelijken met een klok die reset elke keer dat hij een bepaald uur bereikt, maar waarvan de wijzers bewegen met een snelheid die verandert met de grootte van de klok zelf. Naarmate het totaal aantal stenen toeneemt, beweegt de kritieke reeks van deelgroottes omhoog. De waarschijnlijkheid van een verliezende positie hangt ervan af of deze bewegende reeks een even of oneven aantal delen bevat. De pariteit van het aantal delen in deze kritieke reeks is de belangrijkste drijfveer achter de oscillatie. Omdat de distributie van delen wordt beheerst door een wet die lijkt op een Poisson-verdeling, oscilleert de kans op een even aantal delen in deze reeks. Deze oscillatie creëert het zaagtandpatroon. Het onderzoek bevestigt dat de genormaliseerde waarschijnlijkheid niet convergeert naar één getal, maar het hele interval tussen één en twee keer een specifieke schaleringsfactor vult.

De studie breidt zich ook uit voorbij alleen de verliezende posities. Het laat zien dat ditzelfde oscillerende gedrag van toepassing is op elke specifieke, vaste doeluitkomst, niet alleen op het resultaat nul. Voor elke vaste doelnim-som heeft de dichtheid dezelfde eerste-orde verval, en na dezelfde normalisatie volgt het hetzelfde dyadische zaagtandprofiel. Dit suggereert dat de binaire structuur van het spel een permanente handtekening achterlaat op de willekeurige distributie van stapels, een handtekening die weigert te worden gladgestreken door de enorme omvang van de getallen betrokken zijn.

Om deze theoretische voorspellingen te verifiëren, voerde de auteur exacte berekeningen uit voor elke mogelijke schikking van stenen tot een totaal van twintig duizend. Dit vereiste een geavanceerde computationele aanpak die het probleem behandelde als een massale tel-oefening, gebruikmakend van gespecialiseerde algoritmen om de exacte aantallen te bepalen zonder elke individuele combinatie apart op te sommen. De resultaten van deze berekeningen kwamen met opmerkelijke precisie overeen met de theoretische voorspellingen, wat bevestigde dat het zaagtandpatroon echt is en geen artefact van het wiskundige model. De gegevens toonden aan dat de genormaliseerde waarschijnlijkheid stijgt en daalt exact zoals de theorie voorspelde, waarbij de scherpe transities plaatsvinden op de precieze momenten waarop de natuurlijke schaal een macht van twee kruist.

Het onderzoek verdiept zich ook in de aard van de overgang tussen deze pieken en dalen. Hoewel de grafiek scherpe sprongen lijkt te hebben, wordt de schijnbare sprong in werkelijkheid binnen een steeds kleiner wordend venster gladgestreken tot een geleidelijke verschuiving, die wordt bepaald door of het aantal delen in de kritieke reeks even of oneven is. Naarmate het totaal aantal stenen toeneemt, wordt het venster waarin deze afvlakking plaatsvindt nauwer, waardoor de sprongen er steeds scherper uitzien voor het blote oog, ook al blijven ze wiskundig continu. Dit fenomeen verklaart waarom het patroon er zo grillig uitziet in de data, zelfs wanneer de onderliggende wiskunde vloeiend is.

Uiteindelijk biedt dit werk een volledige beschrijving van hoe verliezende posities verdeeld zijn in het spel Nim wanneer de beginconfiguratie willekeurig wordt gekozen. Het lost een langlopende vraag op over de frequentie van deze posities, door aan te tonen dat ze niet een eenvoudig, stabiel traject volgen. In plaats daarvan worden ze beheerst door een complexe interactie tussen de grootte van de stapels en de binaire structuur van het spel. De bevindingen benadrukken een breder principe in de wiskunde: zelfs in systemen die willekeurig en vloeiend lijken, kunnen diepe rekenkundige structuren persistente, scherpe patronen creëren die weerstand bieden aan middeling. De binaire aard van het spel zorgt ervoor dat een specifieke blok informatie zichtbaar en invloedrijk blijft, ongeacht hoe groot het systeem ook wordt, wat een ritme creëert dat zich oneindig herhaalt naarmate de getallen groter worden.