De standaard Rubikkubus heeft het formaat 3 × 3 × 3

De Rubikkubus – grote hit uit de jaren tachtig van de vorige eeuw – heeft ook de wiskundige gemeenschap aardig beziggehouden. De standaard Rubikkubus heeft het formaat 3 × 3 × 3: deze kubus heeft negen kleurrijke vakjes op elke zijde. De kubus is opgelost als alle kanten eenzelfde kleur hebben. Vorig jaar werd bewezen dat het maximale aantal stappen nodig om een Rubikkubus op te lossen (‘Gods getal’) gelijk is aan 20.

Gods getal voor grotere kubussen

Deze zomer hebben Erik Demaine – informaticus aan het Massachusetts Institute of Technology – en een aantal collega’s een algoritme gepresenteerd dat gebruikt kan worden voor het oplossen van willekeurig grote Rubikkubussen. Daarmee kunnen ze berekenen van welke orde van grootte Gods getal is voor een n x n x n kubus. Zij vonden dat het aantal stappen dat nodig is voor het oplossen van een n x n x n kubus voor voldoende grote waarden van n, proportioneel is met n² / log n. Dat betekent dat je twee constantes a en b, en een derde getal N kunt vinden, zodanig dat voor elke n > N geldt dat Gods getal voor een n x n x n kubus tussen a · n² / log n en b · n² / log n ligt.

Een grotere Rubikkubus: 5 × 5 × 5.

Lage complexiteit

Deze onder- en bovengrens van Gods getal lijken behoorlijk grof. Toch geeft het resultaat een heel goed beeld van hoeveel een Rubikkubus moeilijker wordt om op te lossen naarmate het aantal vierkantjes van de kubus toeneemt. En dat blijkt heel erg mee te vallen.

In de complexiteitstheorie spreekt men van een moeilijk probleem (in vakjargon NP-probleem) indien het aantal stappen dat nodig is om tot de oplossing te komen, een exponentiële functie is, bijvoorbeeld 2ⁿ. En dat is hier niet het geval. Bekijk onderstaande figuur maar eens. Je ziet dat de grafiek van de functie 2ⁿ (exponentieel) heel hard stijgt, de grafiek van n² (polyominaal, dus niet exponentieel) minder en de grafiek van n² / log n nog minder. Het plaatje maakt duidelijk dat de Rubikkubus niet heel veel moeilijker wordt naarmate het aantal vakjes toeneemt. Of, zoals wiskundigen het graag zeggen: de Rubikkubus heeft een lage complexiteit.

Effectieve methode

Om de waarde n² / log n te vinden, heeft Demaine een truc bestudeerd die veel kubusoplossers toepassen: het verplaatsen van een enkel vakje naar de juiste positie terwijl alle andere vakjes zo veel mogelijk op hun plaats blijven. Het was al bekend dat het aantal stappen dat nodig is om een kubus met deze techniek op de lossen proportioneel is met n²; dat volgt uit het feit dat een n x n x n kubus 6n² vakjes heeft.

Demaine en zijn collega’s hebben de methode effectiever gemaakt door zich niet op een enkel vakje te concentreren, maar door groepen vakjes die dezelfde richting op moeten tegelijk te verplaatsen. Daarmee konden ze n² reduceren met een factor 1 / log n.

Open vragen

Er zijn nog altijd veel vragen omtrent de Rubikkubus onbeantwoord. De eerste vraag waar Demaine zich mee bezig wil houden, is om de benadering n² / log n precies te maken voor iedere n. Ook zijn ‘Gods getallen’ voor alle Rubikkubussen groter dan 3 × 3 × 3 nog onbekend.

Zie ook:

• Rubikkubus in slechts 26 stappen (Kennislinkartikel)
• Rubik’s cubes of any size can now be solved (artikel in NewScientist)
• How hard is the Rubik’s cube? (artikel in +Plus Magazine)
• Algorithms for Solving Rubik’s Cubes (het artikel van Demaine et al., pdf)