Heel ver weg van dit kinderlijke spelletje treffen we de ontoegankelijke wereld van de abstracte wiskunde aan. Vreemd genoeg hebben deze uitersten met elkaar te maken. In dit verhaal zal ik proberen ook voor niet-wiskundig geschoolden deze verrassende kwestie uit de doeken doen. Mijn inspiratiebron is een hoofdstuk uit het boek Priemwoestijnen van Alex van den Brandhof.
Oerversie
De spelregels kent iedereen: in een vierkant met drie maal drie vakjes moeten spelers om de beurt een kruisje of een rondje zetten: wie het eerst drie kruisjes of rondjes op een rij heeft (horizontaal, verticaal, of diagonaal) wint. Kruisjes en rondjes zetten worden in dit betoog vervangen door vakjes rood of blauw te kleuren. Bovendien gebruiken we de bondiger Engelse term tic-tac-toe in plaats van Boter, Kaas en Eieren.
Figuur 1
Vb 1 Vb2In beide voorbeelden in Figuur 1 wint rood van blauw op overtuigende wijze. De rode en blauwe vakjes zijn afwisselend door de spelers ingekleurd.
Zelfs bij kinderen gaat tic-tac-toe na drie potjes al snel vervelen. Ik moet bekennen dat ik niet lang geleden van mijn dochter heb verloren, maar dat kwam omdat mijn dochter volwassen en erg slim is en ik werd afgeleid doordat onze kat in mijn gezicht begon te likken.
Kortom, tic-tac-toe in deze vorm is niet een spel dat uitnodigt wereldkampioenschappen te organiseren. En in de bibliotheek zijn ook geen planken gevuld met boeken over openingstheorie, zoals het geval is bij schaken of dammen.
Hoe kunnen we het spel spannender maken? Uitbreidingen met meer vakjes en zelfs meer dimensies? Als eis stellen dat een speler altijd wint, dus remise onmogelijk is?
Meer vakjes
Waarom zouden we ons beperken tot 3 x 3 vakjes? Tic-tac-toe met 4 x 4, 5 x 5 enzovoort hokjes is wellicht uitdagender. Vb1 en Vb2 in Figuur 1 noemen we 2-dimensionaal-formaat-3 tic-tac-toe. In Figuur 2 staat een voorbeeld van 2-dimensionaal-formaat-4 tic-tac-toe.
Figuur 2
Of hogere formaat tic-tac-toe nu zoveel leuker is voor kinderen, weet ik niet. 2-dimensionaal-formaat-20 tic-tac-toe duurt in ieder geval lang en pubers kunnen ermee wellicht de peilloze leegte in hun bestaan vullen als ouders voor straf hun mobiel hebben afgepakt.
Drie dimensies
Ik noemde de verveling die toeslaat als je een paar potjes tic-tac-toe speelt (2-dimensionaal-formaat-3) tic-tac-toe. Wordt het interessanter als we tic-tac-toe in hogere dimensies gaan spelen?
Bij een Duitse internetspeelgoedwinkel trof ik een bouwpakket aan voor een driedimensionale versie van tic-tac-toe. Het viel niet mee om die in elkaar te zetten, maar met behulp van heel wat geboor en gezaag en met hulp van een manueel begaafde vriend is het gelukt. Hieronder het trotse resultaat:
Figuur 3
Terwijl bij 2-dimensionaal-formaat-3 tic-tac-toe (de oerversie) er 8 manieren zijn om alle vakjes in een rijtje rood of blauw in te vullen (drie horizontaal, drie verticaal, twee diagonaal), zijn er bij de 3-dimensionaal-formaat-3 versie veel meer mogelijkheden, namelijk 53. Hieronder zijn twee opties weergegeven. De roodgekleurde vakjes verwijzen naar de winnende speler. Blauw maakt er een beetje een potje van.
Figuur 4
3-dimensionaal-formaat-3 tic-tac-toe kan je ook eenvoudig spelen met drie afzonderlijke vierkantjes (2-dimensionaal-formaat-3) die je op een kladblaadje kan krabbelen. Je moet dan wel enig ruimtelijk voorstelling hebben om te bepalen wanneer er drie vakjes op een rij op treden in de kubus. Hetzelfde spel als bij Vb2 in figuur 4 ziet er in dit geval zo uit. Rood wint dus. Vergeet niet dat blauw een beetje dom speelt.
Figuur 5
Vier dimensies
Kunnen we tic-tac-toe in vier dimensies spelen? Daarvoor hebben we een 4-dimensionale superkubus nodig. Voor het geval van formaat-3 heeft zo'n kubus 3 x 3 x 3 x 3 = 81 vakjes. Hogere dimensies komen voor in sciencefiction films of bij geleerden, die zich met theoretische natuurkunde (snaartheorie) of sterrenkunde bezig houden. Is het hele idee daarom absurd?
Nee! We kunnen hogere dimensies begrijpen door vanuit één dimensie lager te denken.
Dit wordt in een ander verband uit de doeken gedaan in de onder wiskundigen beroemde, klassieke roman Flatland (geschreven in 1884) over wezens die in een plat vlak wonen en zich de derde dimensie niet kunnen voorstellen. Naar analogie kunnen wij een beetje de vierde dimensie begrijpen. Net als wij de wezens in het vlak (dat zijn in Flatland onder meer cirkels) vanuit de derde dimensie in hun binnenste kunnen prikken zonder hun buitenkant (een cirkel) te beroeren, kunnen vier-dimensionale wezens vanuit de vierde dimensie ons in onze darmen prikken zonder onze huid aan te raken.
Bij 4-dimensionaal-formaat-3 tic-tac-toe blijven de principes hetzelfde: een speler moet een rijtje van 3 hokjes kleuren in horizontale, verticale of diagonale richting.
In het 3-dimensionale geval kan een horizontaal, verticaal of diagonaal rijtje zich uitstrekken over de verschillende lagen van de kubus (zie figuur 3 en 4).
In het 4-dimensionale geval strekken die rijtjes (lengte 3) zich uit over de hele superkubus .
(horizontaal, verticaal of diagonaal), maar nu ook in richtingen die we ons als simpele driedimensionale sukkels niet kunnen voorstellen.
Hoe kunnen we 4-dimensionaal tic-tac-toe begrijpen, door vanuit een dimensie lager te denken?
We hebben al gezien dat we 3-dimensionaal-formaat-3 tic-tac-toe kunnen spelen met drie 2-dimensionaal-formaat-3 vierkantjes (zie figuur 5)
Op vergelijkbare wijze kunnen we 4-dimensionaal-formaat-3 tic-tac-toe spelen met drie 3-dimensionale-formaat-3 kubussen.
Figuur 6
We zien dat het rode rijtje zich diagonaal dwars door de drie kubussen uitstrekt. Rood wint, ook al omdat Blauw er met zijn gedachten niet zo erg bij is. De winst komt tot stand op een manier die bij een 'gewoon' 3-dimensionaal spel onmogelijk is.
We kunnen nog verder vereenvoudigen. Ieder van deze drie kubussen rafelen we uit elkaar in ieder drie tweedimensionale vierkanten (Zie figuur 4 en 5). Je krijgt dan negen vierkanten uiteengerafeld van drie kubussen met drie lagen. Per zet moeten we dan een van de negen vakjes in een van de negen vierkanten rood of blauw kleuren. Bepalen hoe je tot een een winnend 4-dimensionaal rijtje kan komen, vereist bijna bovenmenselijke concentratie.
Getallenrijen
Omdat we nu eenmaal in een maatschappij leven waar diversiteit hoog gewaardeerd wordt moeten we ook rekening houden met medemensen die om religieuze redenen bezwaar hebben tegen het tekenen van vierkanten of het rommelen met kubussen. Voor hen is er ook een oplossing.
Aan elke cel van een vierkant, kubus of superkubus voegen we voor de overzichtelijkheid een rijtje getallen toe op de volgende wijze.
Figuur 7
Bovenstaand spel verloopt bijvoorbeeld als volgt uitgedrukt in getallenrijtjes,
3332
1111
1131
2222
3323
3333
Dus, samenvattend, in plaats van een fysiek vakje te kleuren schrijft de speler op het blaadje een rijtje cijfers dat overeenkomt met dat vakje (volgens bovenbeschreven systeem). Voor de duidelijkheid doet hij/zij dit met een potlood in zijn kleur (rood of blauw). Als er op deze manier een aantal rijtjes zijn neergekrabbeld in afwisselende kleuren, kunnen we de volgende vuistregel toepassen:
Een speler heeft een winnend rijtje als in de drie overeenkomstige getallenrijtjes op dezelfde positie hetzelfde getal staat of in dezelfde rijtjespositie de getallen oplopen of aflopen (1,2,3 of 3,2,1).
Dit is niet onmiddellijk in te zien, maar je kan het in bovenstaande tabel makkelijk controleren: Rood heeft op alle posities in zijn getallenrijtjes oplopende waarden (1,2,3) onder kubus, laag en per laag: verticaal, horizontaal. Blauw, de verliezer, heeft op overeenkomstige posities, (3,1,3)(3,1,3)(3,3,2) en (2,1,3) en voldoet inderdaad niet aan de overwinnaarscriteria. Wat we hier doen is in feite precies hetzelfde als hokjes kleuren in Figuur 7. Rood mag precies dezelfde champagnefles ontkurken.
Als rood er daarna in slaagt bij een 5-dimensionaal-formaat-3 spel de volgende rijtjes te produceren dan wint hij opnieuw en moet oppassen dat hij niet dronken wordt van de champagne. Om dit te spelen moet hij van de vijfde dimensie afdalen naar de vierde en redeneren vanuit 4-dimensionale superkubussen.
Figuur 9
Superkubussen kunnen we ons niet voorstellen maar gelukkig kunnen we de vuistregel toepassen op de volgende korte weergave van de getallenrijtjes.
21321
12313
22123
22322
32131
32331
De getallen in de drie rode rijtjes zijn op overeenkomstige posities of gelijk of lopen op en af. Voor de blauwe rijtjes is dit niet het geval. Voor de volledigheid, het opschrijven van deze getallenrijtjes is weer equivalent me het inkleuren van hokjes in de 5-dimensionale-formaat-3 superkubus. Probeer dat maar eens!
Als we het spel met getallenrijtjes spelen hebben we eigenlijk helemaal geen (super) kubussen, of vierkanten meer nodig. We kunnen willekeurig-dimensionale spellen van willekeurig formaat spelen zonder ons af te vragen af te vragen wat de getallen precies betekenen. Het enige wat vereist is, is concentratie om, als je aan de beurt bent, getallenrijtjes zo in te vullen dat we op overeenkomende posities de juiste getallen verschijnen of te voorkomen dat de tegenstander dit voor elkaar krijgt. Dat wil zeggen, gewoon de vuistregel toepassen.
We kunnen op deze manier op een kladblaadje ingewikkeld zitten te tic-tac-toe-en, maar het spel lijkt dan wel gedegradeerd tot een soort boekhouden. De opwindende illusie dat we al tic-tac-toe-end in geheimzinnige, occulte hoog-dimensionale ruimtes opereren gaat verloren.
Meer dan twee spelers
Niets belet ons met meer dan twee spelers te spelen. Een 3-dimensionaal-formaat-3 tic-tac-toe voor drie spelers ziet er dan als volgt uit
Figuur 10
Speler groen heeft spelers rood en blauw verslagen
Remise onmogelijk?
Als je toch een spelletje aan het spelen bent, moet liefst iemand winnen of verliezen. Onbeslist betekent in tic-tac-toe dat alle vakjes zijn gekleurd, maar dat geen van de spelers een rijtje van het specifieke formaat in zijn kleur heeft opgesmukt. Echter, remise is een beetje saai, je zou bijna zeggen behoorlijk suf. Twee spelers zijn nooit precies even goed in tic-tac-toe en dat moet in de uitslag tot uitdrukking komen. Ik ben voorstander van een competitieve samenleving, weg met dat egalitaire. We zoeken dus naar versies van tic-tac-toe waar remise onmogelijk is.
Dit vereist enig onderzoek.
We gaan uit van twee spelers.
2-dimensionaal-formaat-2 tic-tac-toe
Figuur 11
Onmiddellijk is te zien dat hoe blauw ook speelt; rood altijd wint. De beginner zegeviert altijd. In tehuizen voor demente bejaarden schijnt deze versie opgang te maken, omdat de spelers bij het volgende potje toch al vergeten zijn wie begonnen en gewonnen heeft.
Het spel kan verlopen als in Figuur 11 weergegeven:
Figuur 12
Hieruit blijkt dat remise inderdaad mogelijk is. Niemand is er in geslaagd een winnend rijtje te produceren.
3-dimensionaal-formaat-3 tic-tac-toe
Van den Brandhof legt in zijn hieronder genoemde boek op niet-wiskundige wijze uit dat bij deze versie remise onmogelijk is. De beginner kan, als hij zich niet vergist, altijd winnen.
Op grond van deze drie voorbeelden kunnen we het vermoeden formuleren dat als het formaat gelijk is aan het aantal dimensies remise onmogelijk is: een van de spelers wint gegarandeerd, zoals we gezien hebben voor 2-dimensionaal-formaat-2 en 3-dimensionaal-formaat-3 tic-tac-toe.
Het heeft heel wat zweet en tranen gekost maar wiskundigen hebben deze hypothese inderdaad bevestigd voor het algemene geval. Stel dat twee spelers een 8-dimensionaal-formaat-8 potje tic-tac-toe spelen (dwz op een acht-dimensionale superkubus die uit 8 x 8 x 8 x 8 x 8 x 8 x 8 x 8 vakjes bestaat). Dan weten we dus zeker dat een van de spelers wint, omdat de dimensionaliteit gelijk is aan het formaat, namelijk 8.
Met drie of meer spelers wordt het andere koek. Wiskundigen hebben ook voor dit geval een diepe stelling geformuleerd: Voor elk formaat k (k mag dus groter dan drie zijn) en aantal spelers r (r mag dus groter dan 2 zijn) bestaat er een getal n zodat de n-dimensionale-formaat-k versie van tic-tac-toe met r-spelers altijd een winnaar heeft. Bijvoorbeeld voor formaat-134 tic-tac-toe voor 28 spelers kan gespeeld worden in een aantal dimensies zodanig dat een van de 28 spelers gegarandeerd wint.
Er zit wel een addertje onder het gras. De heren mathematici blijven in zoverre in gebreke dat ze ons niet kunnen vertellen hoe groot n, het aantal dimensies dan wel moet zijn, gegeven het formaat en het aantal spelers (indien groter dan twee).
Maar we kunnen gerust gaan slapen in de wetenschap dat het betreffende aantal dimensies in ieder geval daadwerkelijk ergens rondzweeft.
Van den Brandhof wijst er in zijn boek op dat bovengenoemde stelling is een speciaal geval van het dichtheidstheorema van Hales en Jewett:
Deze stelling is bewezen door samenwerking van 27 wiskundigen in het internet Polymath project en de resultaten zijn gepubliceerd in het prestigieuze wiskundetijdschrift Annals of Mathematics.
Ikzelf heb geen idee waar dit theorema over gaat, laat staan dat ik het bewijs in genoemd tijdschrift zou kunnen doorgronden. Maar, inzicht of niet, onverkort geldt dat onze reis van een kinderachtig spelletje naar de indrukwekkende bergtoppen van de hogere wiskunde voert.
Het is aan de lezer om te beoordelen of de versies van tic-tac-toe die de revue zijn gepasseerd ook maatschappelijke relevant zijn.
Literatuur
Alex van den Brandhof, Priemwoestijnen. Hoogtepunten uit de wiskunde van de 21ste eeuw, 2019
Edwin Abbott, Flatland, A romance of many dimensions, 1884.




















