de kubus van rubik was dé puzzelrage van de jaren 1980 en is nog steeds populair als breinbreker. tientallen miljoenen zijn ervan verkocht. vele liggen in een vergeten hoekje stof te verzamelen, de blokjes in de war. andere worden regelmatig geolied door speedcubers, die op internationale bijeenkomsten strijden om hun kubus het snelst op te lossen. nog andere worden bestudeerd door wiskundigen. recent werd aangetoond dat twintig bewegingen volstaan om de kubus op te lossen.

De kubus van Rubik als wiskundige uitdaging (#40)

Paul Igodt, Mats Vermeeren, Stijn Vermeeren

De kubus werd niet uitgevonden door een wiskundige of een puzzelmaker. Ernő Rubik, geboren in 1944, was hoogleraar in de architectuur in Boedapest, Hongarije. In de eerste plaats was hij gefascineerd door een constructieprobleem. Hoe kun je kleine kubusjes samenvoegen tot een grote kubus (3 x 3 x 3), waarvan alle zijkanten onafhankelijk van elkaar kunnen ronddraaien? Een eerste poging, waarbij de blokjes met elastiekjes bij elkaar werden gehouden, faalde omdat de bewegingen van de kubus de elastiekjes deden breken. Uiteindelijk bedacht Rubik een eenvoudig maar zeer ingenieus mechanisme zonder elastiekjes, waarbij de blokjes als het ware elkaar vasthouden. Het (denkbeeldige) middelste blokje van de kubus werd door Rubik vervangen door heel nauwkeurig in elkaar passende vormen, vast verbonden met de buitenste blokjes (die wel zichtbaar zijn). Die in elkaar passende vormen zijn precies zó gemaakt dat de zijkanten van de kubus de gewenste beweeglijkheid hebben.

Dit inzicht in een ruimtelijk technisch probleem was echter slechts de aanzet tot iets wat ook Rubik niet zal hebben vermoed. Rubik was geboeid door hoe de kleine kubusjes zich herschikten als hij aan de kubus draaide. Om de beweging van die blokjes beter te kunnen volgen, gaf hij aan elk zijvlak van de kubus een andere kleur. Na slechts enkele draaiingen bleek het al erg moeilijk om de kleuren terug naar hun oorspronkelijke posities te brengen. Zo bezorgde Rubik een uitdagend probleem van een fascinerende schoonheid aan miljoenen mensen, amateurs en wiskundigen, puzzelaars en informatici. De eerste kubussen kwamen in Hongarije op de markt in 1977. Daar was het spel niet meteen een groot succes. Toen de kubus drie jaar later aan de andere kant van het IJzeren Gordijn op de markt kwam, zorgde een westerse marketingmachine ervoor dat hij al snel een ongelofelijke rage werd.

Wie voor het eerst even experimenteert met de kubus van Rubik, brengt hem al snel hopeloos in de war. Wat je ook probeert, het lijkt verre van evident om de blokjes weer allemaal op hun originele plaats te krijgen. Chaos dreigt, moed en volharding volstaan niet. Enkele blokjes op de juiste plaats brengen lukt nog wel, maar hoe kun je de rest van de puzzel oplossen zonder diezelfde blokjes opnieuw te gaan verplaatsen? Vele puzzelaars zoeken uiteindelijk een oplossing in boeken of op het internet. Die oplossingen bestaan meestal uit een aanzienlijk aantal tussenstappen. Kan het beter, en in hoeveel stappen dan wel? Wat is de meest efficiënte oplossingsmethode?

Enkele blokjes op de juiste plaats brengen lukt nog wel, maar hoe kun je de rest van de puzzel oplossen zonder die blokjes opnieuw te gaan verplaatsen?

Om inzicht te krijgen in het probleem moeten we eerst de bewegingen van de kubus beter begrijpen. Dit begint met een grondige beschrijving van alle mogelijke bewegingen. Een kubus heeft zes zijvlakken en telt dus zes kleuren. Als we de kubus vanuit een vast standpunt bekijken, kunnen we de zijvlakken eenvoudig benoemen: voor (V), achter (A), links (L), rechts (R), boven (B) en onder (O). Deze namen brengen we aan op de centrale vlakjes in elk zijvlak. De kleur van die middelste vlakjes bepaalt immers de kleur die het volledige zijvlak krijgt. De basisbewegingen van de kubus zijn kwartdraaien van elk van de zes zijvlakken. Geen van die kwartdraaien verplaatst de centrale vlakjes van de zijvlakken. Op elk zijvlak zijn er dus slechts acht vlakjes die wél bewegen en gevolgd moeten worden tijdens de kwartdraaien. Voor de zes zijvlakken samen moeten we bijgevolg 48 vlakjes volgen. Elke transformatie van de kubus is daarom vrij eenvoudig neer te schrijven als een permutatie of onderlinge herschikking van deze 48 zijvlakjes. Men kan dit als volgt doen: vlakje 1 gaat naar vlakje a, vlakje 2 gaat naar vlakje b, vlakje 3 gaat naar vlakje c, enzovoort. Ietwat naïef zou je kunnen vermoeden dat er 48 mogelijkheden zijn voor a, daarna 47 mogelijkheden voor b, 46 voor c, en zo verder. Dit suggereert dat er 48 x 47 x 46 x … x 2 x 1 mogelijkheden zouden zijn.

Dit is echter wat kort door de bocht: sommige vlakjes staan nu eenmaal op hetzelfde kleine blokje en kunnen dus niet zomaar los van elkaar worden verplaatst. Ook kan een kubusje dat zich aan een hoekpunt van de grote kubus bevindt, en dus drie zichtbare vlakjes heeft, onmogelijk ergens in het midden van een ribbe van de grote kubus belanden, want daar zit een blokje met slechts twee zichtbare vlakjes. Er zijn in werkelijkheid heel wat minder mogelijkheden, en dat is maar goed ook. Het juiste aantal mogelijkheden om de kubus met kwartdraaien te transformeren bedraagt nog altijd 43 252 003 274 489 856 000, een getal met maar liefst twintig cijfers. Alleen al dit onuitspreekbare getal suggereert dat het geen eenvoudige opgave wordt om de kubus op te lossen. Als de kubus eenmaal in de war is gebracht, dan is er juist één transformatie die hem terug in de oorspronkelijke positie brengt. Die ene transformatie moet je opsporen in een verzameling van miljoenen keren miljoenen mogelijkheden.

Wiskundigen proberen graag inzicht te verwerven in een probleemstelling door structuur te ontdekken. Niet het krachtig rekenen of de grote getallen wijzen op wiskundige kracht, maar wel de inzichtelijke bonus die ontstaat door structuur te ontdekken. Zo bekeken is de kubus van Rubik ook vandaag nog een pareltje voor het wiskundeonderwijs, en juist daarom een veel terugkerend voorbeeld in diverse universitaire cursussen en zelfs een maatstaf om de snelheid van diverse computeralgoritmen met elkaar te vergelijken.

In het geval van de kubus bestaat de vondst erin dat we kunnen rekenen met de transformaties die de kubus vervormen

In het geval van de kubus bestaat de vondst erin dat we kunnen rekenen met de transformaties die de kubus vervormen. Zoals bij elke berekening hebben we hiervoor een gepaste bewerking nodig. Die gaat als volgt. Onder een zijvlak verstaan we de negen kleine blokjes die samen een zijkant van de kubus vormen. De kubus heeft zes zijvlakken, en door telkens weer een zijvlak één of meerdere kwartdraaien te draaien, verkrijgen we om het even welke transformatie van de kubus. Als we voor elk zijvlak opteren voor een kwartdraai in wijzerzin (gezien vanuit een frontaal aanzicht), en hiervoor ook de letters V, A, L, R, B en O schrijven, dan kan het letterwoord ‘VVLRVOB’ worden gelezen als: kwartdraai vooraan, dan kwartdraai vooraan, dan kwartdraai links, dan kwartdraai rechts … Elke transformatie van de kubus valt dus te schrijven als een dergelijk ‘woord’. Als we verschillende transformaties na elkaar uitvoeren, is het uiteindelijke effect een transformatie die beschreven wordt door de woorden van alle uitgevoerde transformaties na elkaar te schrijven tot één lang woord. Een verzameling (van bijvoorbeeld transformaties of getallen) waarbij we elke twee elementen kunnen combineren tot een nieuw element, en waarbij die combinatiemethode of ‘bewerking’ aan bepaalde, steeds weer dezelfde regels voldoet, wordt in de wiskunde een ‘groep’ genoemd. We zeggen dan ook dat die verzameling een groepsstructuur draagt. Dit begrip werd rond 1870 voor het eerst formeel ingevoerd door de Engelse wiskundige Arthur Cayley. De transformaties van een kubus van Rubik zijn een voorbeeld van een groep: Rubiks groep. De elementen van de groep kunnen we neerschrijven als woorden met de letters V, A, L, R, B en O (de zijvlakken van de kubus), en de bewerking bestaat erin twee dergelijke woorden samen te voegen tot een nieuw woord door ze na elkaar te schrijven.

Het lijkt bijzonder eenvoudig, maar er zijn toch een paar delicate aspecten aan Rubiks groep. Bedenk even wat het woord ‘VVVV’ betekent. Dit staat voor een kwartdraai rechts aan het voorvlak van de kubus, en dat vier keer na elkaar. Als je vier keer aan hetzelfde zijvlak een kwartdraai geeft, dan kom je terug in je oorspronkelijke positie. Je had dus evengoed niets kunnen doen, net zoals een vermenigvuldiging met het getal 1 ook geen nieuw resultaat oplevert. Daarom geldt in de groep van Rubik dat ‘VVVV = 1’. Op analoge wijze geldt dit ook voor elk van de vijf andere kwartdraaien (A, L, R, B en O). Wil je dus een kwartdraai ongedaan maken, dan kun je ofwel die kwartdraai in tegengestelde zin uitvoeren, ofwel die kwartdraai nog drie keer na elkaar uitvoeren. In een groep schrijven we dat ‘V4 = 1’ of ook ‘V-1 = V3’. Willen we dus de transformatie T = VBLL ongedaan maken, dan volstaat het ze te laten volgen door ‘LLBBBVVV’ want dan verkrijgen we VBLL LLBBBVVV = VB 1 BBBVVV = V1VVV = 1. De algebraïst noemt dit de ‘inverse transformatie’ en zal ‘T-1 = L2B3V3’ schrijven. Dit zijn slechts enkele voorbeelden van wat groeptheoretici ‘relaties’ in de groep van Rubik noemen, de ‘spelregels’, zou je ze ook kunnen noemen.

Met deze eenvoudige principes kunnen we de oplossing van de kubus van Rubik herformuleren als een algebraïsch probleem. Als iemand de kubus heeft getransformeerd, met bijvoorbeeld de transformatie T, dan moeten we proberen die T te schrijven als een woord in de letters V, A, L, R, B, O, en daarna de inverse transformatie T-1 bepalen, eveneens als een woord in dezelfde letters. In principe weten we dan welke kwartdraaien we moeten uitvoeren om de kubus terug in zijn oorspronkelijke positie te plaatsen. Een dergelijk probleem kun je in feite in nagenoeg elke groep stellen. Reeds in 1911 formuleerde de Duitse wiskundige Max Dehn dit ‘woordprobleem’ in de groepentheorie. De kubus oplossen is dus niets anders dan het in 1911 gestelde woordprobleem oplossen in de groep van Rubik. Zouden we zoiets dan niet beter aan een computer overlaten? Die kan toch vele keren sneller rekenen dan wij? Inderdaad, maar het aantal mogelijkheden is ook zo overdonderend groot, dat een onoordeelkundige brute force aanpak zelfs de snelste computers klein krijgt. Wiskundig inzicht moet het hier halen op rekenkracht. Net zoals ruimtelijk inzicht en de beheersing van enkele snelle transformaties de speedcuber helpen om in luttele seconden te doen wat wij hier beschrijven, en dit als het ware zonder te rekenen.

In de twintigste eeuw heeft de groepentheorie zich ontwikkeld tot een uiterst belangrijk onderzoeksgebied in de wiskunde, dat raakvlakken heeft met tal van andere disciplines, waaronder de meetkunde, de analyse, maar ook heel veel toegepaste realisaties, zoals cryptosystemen. In de cryptografie bestudeert men onder andere systemen die het mogelijk maken op een eenvoudige en snelle manier informatie om te zetten in een code (te versleutelen), maar op zo’n manier dat de omgekeerde operatie (het ontcijferen) bijzonder moeilijk is of slechts door het kennen van extra informatie eenvoudig wordt. Het versleutelen en ontcijferen komt in verschillende operationele cryptosystemen neer op het rekenen in bepaalde types groepen, soms van erg verrassende aard. Het bestuderen van die groepen is dan ook een geliefd onderzoeksthema.

Onderzoek in de groepentheorie verenigt nog steeds vele honderden wiskundigen over de hele wereld. Zo bestudeerden de Russische wiskundige Pyotr Novikov en zijn Amerikaanse collega William Boone in de jaren 1955-1958 het eerder vernoemde woordprobleem. Ze konden de onbeslisbaarheid van dit probleem aantonen in bepaalde types groepen. In de fameuze Novikov-Boone-stelling wordt het volgende aangetoond: er bestaat een groep, waarin men de woorden schrijft met de letters van een eindig alfabet en waarvan de structuur bepaald wordt door slechts eindig veel relaties, maar die toch zo ingewikkeld is dat het onmogelijk is door een computer te laten narekenen of een gegeven woord gelijk is aan 1. Ook de symmetrieën van elk object, en zelfs van elke theorie, worden typisch als een groepsstructuur bestudeerd. De groep van de kubus van Rubik is een perfect voorbeeld daarvan. Inzicht in die structuur kan dan leiden tot inzicht in het object of de theorie. Het intussen wereldwijd bekende boek Het Symmetrie-monster van Marcus Du Sautoy uit Oxford biedt een schitterende kennismaking met dit aspect van groepentheorie. Meermaals werd ook een Fieldsmedaille uitgereikt voor baanbrekend onderzoek in de groepentheorie. Dit is de hoogste wetenschappelijke onderscheiding in de wereld van de wiskundigen, die de status van een Nobelprijs geniet (hoewel er geen vergelijkbare financiële beloning bijhoort). Fieldsmedailles worden slechts om de vier jaar uitgereikt door de International Mathematical Union, die op dit ogenblik een Belgische voorzitter heeft, Ingrid Daubechies (van Duke University in de Verenigde Staten). Eerder ontvingen onze landgenoten Pierre Deligne en Jean Bourgain een Fieldsmedaille.

De laatste dertig jaar hebben verscheidene wiskundigen geprobeerd om de structuur van de groep van Rubik beter te begrijpen. Met zijn gigantische aantal elementen is dit een enorme uitdaging. Anderzijds is Rubiks groep ook een uitstekend didactisch instrument gebleken om wiskundigen in opleiding te laten kennismaken met diverse probleemstellingen. Er is immers ook een zekere sportieve rekentechnische uitdaging, die kan zorgen voor de nodige prestaties en aandacht. Ook Rubik zelf was enigszins een uitdager, toen hij een variant met 4 x 4 x 4 blokjes ontwikkelde – bekend als Rubiks Revenge – die de complexiteit nog sterk opdreef.

Het getal van God is precies gelijk aan 20

Wat is nu het kleinste aantal stappen (kwart- of halve draaien) waarmee men steeds tot een oplossing kan komen? Ondanks alle aandacht bleef de vraag naar de efficiëntste oplossingsmethode decennia lang een open vraag. Daarom werd dit kleinste aantal stappen ook wel het ‘getal van God’ genoemd, en de bijbehorende oplossingsmethode het ‘algoritme van God’. Door steeds betere wiskundige inzichten en steeds snellere computerberekeningen werd er stapsgewijs vooruitgang geboekt. Zo wist men in 1992 dat er hoogstens 37 stappen nodig waren, een bovengrens voor het getal van God, die tot in 2008 stapsgewijs kleiner gemaakt kon worden. Ook kende men uit eerder onderzoek al een configuratie die exact 20 stappen vereiste, en dus niet in minder bewegingen op te lossen was. In 2010 kwam een samenwerking van wiskundigen en computerwetenschappers tot het ultieme resultaat: het getal is precies gelijk aan 20.

Om de complexiteit van het probleem beter te begrijpen kunnen we even volgende vergelijking maken. Een bepaald vermoeden stelt dat je twee willekeurige mensen op aarde, An en Jef, altijd in zes stappen met elkaar kunt verbinden: An is de kennis van een kennis van een kennis … van Jef. Met ‘six degrees of separation’ ben je met iedereen verbonden. Als dit vermoeden al klopt, dan is het nog steeds een hopeloos complex probleem om voor elke twee mensen die zes stappen te vinden. Nu we weten dat het getal van God gelijk is aan 20, is het dus werkelijk aangetoond dat je elke kubus van Rubik in 20 stappen kunt oplossen. Maar deze 20 stappen ook effectief vinden is nog ettelijke keren complexer dan het vinden van de ‘six degrees of separation’ tussen jou en een andere persoon op aarde.

Om het aantal berekeningen te beperken die nodig zijn voor het vinden van het getal van God, maakten de onderzoekers slim gebruik van de symmetrieën en andere structuren in de groep van Rubik. Zo hoefden ze niet alle 43 252 003 274 489 856 000 posities apart te beschouwen, maar konden zij het probleem zo reduceren tot slechts 2 217 093 120 verschillende gevallen. Om al die gevallen op te lossen kon men een beroep doen op vrije computerrekentijd in de rekencluster van Google. Op een gewone pc zou dit rekenwerk 35 jaar geduurd hebben. Toch is het bijzondere van dit resultaat niet de rekenkracht. Het echte wonder is het feit dat het probleem überhaupt benaderbaar werd door te bouwen op al lang bestaande wiskundige inzichten, die zelf het resultaat waren van vele eeuwen wiskundig onderzoek.

Thomas Rokicki, Herbert Kociemba, Morley Davidson en John Dethridge, ‘God’s number is 20′, http://www.cube20.org, 2010.

Paul Igodt is als wiskundige verbonden aan de KU Leuven Kulak. Mats Vermeeren is wiskundige verbonden aan de Berlin Mathematical School en Stijn Vermeeren is als wiskundige verbonden aan de University of Leeds.