Wiskundigen gooien met dobbelstenen en krijgen steen-papier-schaar

Zoals Bill Gates het verhaal vertelt, daagde Warren Buffett hem ooit uit voor een dobbelspel. Elk zou een van de vier dobbelstenen van Buffett selecteren, en dan zouden ze gooien, waarbij het hoogste aantal zou winnen. Dit waren geen standaard dobbelstenen - ze hadden een ander assortiment van getallen dan de gebruikelijke 1 tot en met 6. Buffett bood aan om Gates eerst te laten kiezen, zodat hij de sterkste dobbelsteen kon kiezen. Maar nadat Gates de dobbelstenen had onderzocht, kwam hij met een tegenvoorstel: Buffett zou als eerste moeten kiezen.

Gates had ingezien dat de dobbelstenen van Buffett een merkwaardige eigenschap vertoonden: geen van hen was de sterkste. Als Gates als eerste had gekozen, dan had Buffett, welke dobbelsteen hij ook had gekozen, een andere dobbelsteen kunnen vinden die hem kon verslaan (dat wil zeggen, een met meer dan 50% kans om te winnen).

Buffett's vier dobbelstenen (noem ze A, B, C en D) vormde een patroon dat deed denken aan steen-papier-schaar, waarin A beats B, B beats C, C beats D en D beats A. Wiskundigen zeggen dat zo'n set dobbelstenen "intransitief" is.

"Het is helemaal niet intuïtief dat [intransitieve dobbelstenen] zelfs zouden moeten bestaan," zei Brian Conrey, de directeur van het American Institute of Mathematics (AIM) in San Jose, die in 2013 een invloedrijk artikel over dit onderwerp schreef.

Wiskundigen bedachten de eerste voorbeelden van intransitieve dobbelstenen meer dan 50 jaar geleden, en uiteindelijk bewezen dat als je kijkt naar dobbelstenen met steeds meer zijden, het mogelijk is om intransitieve cycli van elke lengte te creëren. Wat wiskundigen tot voor kort niet wisten, was hoe vaak onovergankelijke dobbelstenen zijn. Moet je dergelijke voorbeelden zorgvuldig verzinnen, of kun je dobbelstenen willekeurig kiezen en een goede kans maken om een ​​intransitieve set te vinden?

Kijken naar drie dobbelstenen, als je dat weet A beats B en B beats C, dat lijkt het bewijs dat A is de sterkste; situaties waar C beats A zou zeldzaam moeten zijn. En inderdaad, als de getallen op de dobbelstenen mogen optellen tot verschillende totalen, dan geloven wiskundigen dat deze intuïtie klopt.

Maar a papier online geplaatst laat vorig jaar zien dat in een andere natuurlijke setting deze intuïtie spectaculair faalt. Stel dat u vereist dat uw dobbelstenen alleen de nummers gebruiken die op een gewone dobbelsteen voorkomen en hetzelfde totaal hebben als een gewone dobbelsteen. Toen liet de krant zien, als A beats B en B beats C, A en C hebben in wezen gelijke kansen om tegen elkaar te zegevieren.

"Wetende dat A beats B en B beats C geeft u alleen geen informatie over of A beats C, "Zei Timothy Gowers van de Universiteit van Cambridge, een Fields-medaillewinnaar en een van de bijdragers aan het nieuwe resultaat, dat werd bewezen via een open online samenwerking die bekend staat als een Polymath-project.

Ondertussen nog een recente paper analyseert sets van vier of meer dobbelstenen. Die bevinding is misschien nog meer paradoxaal: als je bijvoorbeeld willekeurig vier dobbelstenen kiest en je vindt dat A beats B, B beats C en C beats D, dan is het een beetje meer waarschijnlijk voor D verslaan A dan omgekeerd.

Noch sterk noch zwak

De recente golf van resultaten begon ongeveer tien jaar geleden, nadat Conrey een bijeenkomst voor wiskundeleraren bijwoonde met een sessie over intransitieve dobbelstenen. "Ik had geen idee dat zulke dingen konden bestaan," zei hij. "Ik raakte een beetje gefascineerd door hen."

Hij besloot (later vergezeld door zijn collega Kent Morrisson bij AIM) om het onderwerp te verkennen met drie middelbare scholieren die hij begeleidde: James Gabbard, Katie Grant en Andrew Liu. Hoe vaak, zo vroeg de groep zich af, zullen willekeurig gekozen dobbelstenen een intransitieve cyclus vormen?

Aangenomen wordt dat intransitieve sets dobbelstenen zeldzaam zijn als de cijfers van de dobbelstenen optellen tot verschillende totalen, aangezien de dobbelsteen met het hoogste totaal waarschijnlijk de andere zal verslaan. Dus besloot het team zich te concentreren op dobbelstenen die twee eigenschappen hebben: ten eerste gebruiken de dobbelstenen dezelfde nummers als op een standaard dobbelsteen - 1 tot en met n, in het geval van een n-zijdige dobbelsteen. En ten tweede, de gezichtsnummers tellen op tot hetzelfde totaal als op een standaarddobbelsteen. Maar in tegenstelling tot standaard dobbelstenen, kan elke dobbelsteen enkele getallen herhalen en andere weglaten.

In het geval van zeszijdige dobbelstenen zijn er slechts 32 verschillende dobbelstenen die deze twee eigenschappen hebben. Dus met behulp van een computer kon het team alle triples identificeren waarin A beats B en B beats C. Dat vonden de onderzoekers tot hun verbazing A beats C in 1,756 triples en C beats A in 1,731 triples - bijna identieke nummers. Op basis van deze berekening en simulaties van dobbelstenen met meer dan zes zijden, vermoedde het team dat naarmate het aantal zijden van de dobbelstenen oneindig nadert, de kans dat A beats C benadert 50%.

Het vermoeden, met zijn mix van toegankelijkheid en nuance, leek Conrey goed voer voor een Polymath-project, waarin veel wiskundigen online samenkomen om ideeën uit te wisselen. Medio 2017 stelde hij het idee voor aan Gowers, de grondlegger van de Polymath-aanpak. "Ik vond de vraag erg leuk, vanwege de verrassingswaarde," zei Gowers. Hij schreef een blogpost over het vermoeden dat een golf van reacties opleverde, en in de loop van zes extra berichten slaagden de commentatoren erin het te bewijzen.

In hun krant, gepost online eind november 2022 is een belangrijk onderdeel van het bewijs het aantonen dat het voor het grootste deel geen zin heeft om te praten over de vraag of een enkele dobbelsteen sterk of zwak is. De dobbelstenen van Buffett, die geen van allen de sterkste van het peloton zijn, zijn niet zo ongebruikelijk: als je willekeurig een dobbelsteen kiest, toonde het Polymath-project aan, zal het waarschijnlijk ongeveer de helft van de andere dobbelstenen verslaan en verliezen van de andere helft. "Bijna elke dobbelsteen is redelijk gemiddeld," zei Gowers.

Het project week in één opzicht af van het oorspronkelijke model van het AIM-team: om enkele technische details te vereenvoudigen, verklaarde het project dat de volgorde van de nummers op een dobbelsteen ertoe doet - dus bijvoorbeeld 122556 en 152562 zouden als twee verschillende dobbelstenen worden beschouwd. Maar het Polymath-resultaat, gecombineerd met het experimentele bewijs van het AIM-team, creëert een sterk vermoeden dat het vermoeden ook waar is in het originele model, zei Gowers.

"Ik was absoluut verheugd dat ze met dit bewijs kwamen", zei Conrey.

Als het ging om verzamelingen van vier of meer dobbelstenen, had het AIM-team vergelijkbaar gedrag voorspeld als dat van drie dobbelstenen: als A beats B, B beats C en C beats D dan zou er een kans van ongeveer 50-50 moeten zijn dat D beats A, nadert precies 50-50 naarmate het aantal zijden van de dobbelsteen oneindig nadert.

Om het vermoeden te testen, simuleerden de onderzoekers onderlinge toernooien voor sets van vier dobbelstenen met 50, 100, 150 en 200 zijden. De simulaties volgden hun voorspellingen niet zo nauw als in het geval van drie dobbelstenen, maar waren nog steeds dichtbij genoeg om hun geloof in het vermoeden te versterken. Maar hoewel de onderzoekers het niet beseften, hadden deze kleine verschillen een andere boodschap: voor sets van vier of meer dobbelstenen is hun vermoeden onjuist.

"We wilden echt dat [het vermoeden] waar was, want dat zou cool zijn", zei Conrey.

In het geval van vier dobbelstenen, Elisabeth Cornacchia van het Zwitserse Federale Instituut voor Technologie Lausanne en Jan Hazla van het African Institute for Mathematical Sciences in Kigali, Rwanda, toonde in een papier eind 2020 online geplaatst dat als A beats B, B beats C en C beats Ddan D heeft een iets betere kans dan 50% om te verslaan A - waarschijnlijk ergens rond de 52%, zei Hązła. (Net als bij het Polymath-papier gebruikten Cornacchia en Hązła een iets ander model dan in het AIM-papier.)

De bevinding van Cornacchia en Hązła komt voort uit het feit dat hoewel een enkele dobbelsteen in de regel noch sterk noch zwak zal zijn, een paar dobbelstenen soms gemeenschappelijke krachtgebieden kunnen hebben. Als je willekeurig twee dobbelstenen kiest, lieten Cornacchia en Hązła zien, is de kans groot dat de dobbelstenen gecorreleerd zijn: ze zullen de neiging hebben om dezelfde dobbelstenen te verslaan of te verliezen. "Als ik je vraag om twee dobbelstenen te maken die dicht bij elkaar liggen, blijkt dat dit mogelijk is", zei Hązła. Deze kleine stukjes correlatie duwen de toernooiresultaten weg van symmetrie zodra er ten minste vier dobbelstenen in beeld zijn.

De recente kranten zijn niet het einde van het verhaal. De paper van Cornacchia en Hązła begint pas precies te ontdekken hoe correlaties tussen dobbelstenen de symmetrie van toernooien uit balans brengen. In de tussentijd weten we nu echter dat er tal van sets intransitieve dobbelstenen zijn - misschien zelfs een die subtiel genoeg is om Bill Gates te misleiden om als eerste te kiezen.