211service.com
Rubiks kubus wiskunde
In 2010 bewees een internationaal team van onderzoekers dat, hoe vervormd een Rubiks kubus ook werd, er niet meer dan 20 zetten voor nodig waren om hem op te lossen. Hun bewijs was echter gebaseerd op het equivalent van 35 jaar rekenen op een goede moderne computer.
Voor kubussen die groter zijn dan de standaard Rubik's kubus, is het goed mogelijk om voldoende startposities te onderzoeken buiten de rekencapaciteit van alle computers ter wereld. Maar in september leidde Erik Demaine (rechts), universitair hoofddocent informatica en techniek, een team met onder meer zijn vader, CSAIL gasthoogleraar Martin Demaine (links), dat de wiskundige relatie aantoonde tussen het aantal vierkanten in een kubus en de aantal zetten in de kortste oplossing naar de meest gecodeerde toestand.
De standaardmanier om een Rubiks kubus op te lossen is om een vierkant te vinden dat niet op zijn plaats is en dit op zijn plaats te verplaatsen terwijl de rest van de kubus zo min mogelijk veranderd wordt. Dat levert een worstcaseoplossing op waarvan het aantal zetten evenredig is met N2, waarbij N het aantal vierkanten per rij is. Maar het team zag dat onder bepaalde omstandigheden een enkele reeks wendingen meerdere vierkanten op hun plaats kon brengen.
Het was geen gemakkelijke taak om die omstandigheden wiskundig te beschrijven. In het eerste uur zagen we dat het minimaal N2/log N moest zijn, zegt Erik Demaine. Maar toen duurde het vele maanden voordat we konden bewijzen dat N2/log N genoeg zetten was.