Hoe moeilijk is het om Rubik ‘ s kubus te versleutelen?

Rubik ‘S Cube is al 40 jaar een van’ s werelds favoriete puzzels. Verschillende methoden zijn bedacht om het op te lossen, zoals uitgelegd in talloze boeken. Expert “speedcubers” kan het oplossen in een kwestie van seconden.

naast dergelijke prestaties van verbazingwekkende behendigheid, zijn er veel fascinerende wiskundige vragen gerelateerd aan Rubik ‘ s kubus. Een beweging van de kubus bestaat uit het draaien van een van de zes vlakken met 90, 180 of 270 graden. Maar liefst 43.252.003.274.489.856.000 mogelijke toestanden kunnen worden verkregen door opeenvolgingen van bewegingen toe te passen op de opgeloste toestand.

ondanks deze complexiteit werd in 2010 aangetoond dat Rubik ‘ s kubus altijd kan worden opgelost in 20 zetten of minder, ongeacht de initiële status. Dit getal wordt aangeduid als “God’ s number”, omdat alle bekende oplossingsmethoden die door mensen worden gebruikt doorgaans aanzienlijk meer bewegingen gebruiken dan deze optimale waarde.

Rubik ‘ s Cube in de opgeloste toestand. Mike Gonzalez (TheCoffee)

maar hoe zit het met de tegenovergestelde vraag: hoeveel zetten zijn er nodig om een opgeloste kubus te versleutelen? Op het eerste gezicht klinkt dit als een veel eenvoudiger vraag dan het berekenen van Gods nummer. Immers, in tegenstelling tot het oplossen van een kubus, scrambling men neemt geen enkele vaardigheid.

soortgelijke vragen zijn met succes beantwoord Voor kaarten schudden. Een beroemd voorbeeld is de studie van 1990 van de “riffle shuffle” door wiskundigen Dave Bayer en Perci Diaconis. Een kaartspel wordt gedefinieerd als “gemengd” als de volgorde willekeurig is, waarbij elke mogelijke volgorde dezelfde kans heeft om te verschijnen. Bayer en Diaconis toonden aan dat zeven riffle shuffles nodig en voldoende zijn om ongeveer een standaard spel kaarten te mengen.

vorig jaar publiceerden wiskundigen een soortgelijke studie van de 15 puzzel, die bestaat uit een 4×4 vierkant gevuld met 15 schuivende tegels en een lege ruimte.

wat betekent het om een kubus te versleutelen?

een typische persoon die een Rubik ‘ s kubus probeert te versleutelen, voert herhaaldelijk willekeurige bewegingen op die kubus uit. De resulterende willekeurige opeenvolging van toestanden is een speciaal geval van wat wiskundigen een Markov-keten noemen. De belangrijkste eigenschap is dat gegeven de huidige staat, de waarschijnlijkheid van wat de volgende staat zal zijn niet afhankelijk is van een van de vorige Staten.

door de theorie van Markov ketens toe te passen op kubus-vervorming, volgt hieruit dat naarmate het aantal willekeurige bewegingen toeneemt, de kans op het zijn in een bepaalde van de mogelijke toestanden steeds dichter bij 1/43,252,003,274,489,856,000. Wiskundigen noemen dit een” uniforme kansverdeling”, omdat elke mogelijke toestand met dezelfde waarschijnlijkheid plaatsvindt.

na een bepaald aantal willekeurige bewegingen zal de toestand van de kubus willekeurig zijn, maar de kansverdeling zal niet precies uniform zijn; sommige toestanden zullen eerder voorkomen dan andere.

laat d(t) beschrijven hoeveel de kansverdeling na t willekeurige bewegingen verschilt van de uniforme kansverdeling. Naarmate het aantal willekeurige bewegingen(t) toeneemt, zal de waarde van d (t) afnemen. De kubus die wordt versleuteld komt overeen met D (t) die klein is.

Markov-chain Monte Carlo

In de theorie van Markovketens wordt deze afname in d(t) “mengen”genoemd. Naast kaarten schudden en puzzel scrambling, de theorie van Markov keten mengen heeft ook zeer serieuze praktische toepassingen. Een van de belangrijkste computationele tools in de moderne wetenschap en techniek is de Monte Carlo methode. Deze methode, net als de beroemde casino waarnaar het is vernoemd, is fundamenteel afhankelijk van kans. In essentie, het probeert om ongeveer op te lossen harde wiskundige problemen met behulp van meerdere willekeurige gissingen.

in de praktijk worden Markovketens vaak gebruikt om deze willekeurige toestanden te produceren. Om de nauwkeurigheid van deze Markov-keten Monte Carlo methoden te begrijpen, is de belangrijkste taak om in te schatten hoe snel d(t) afneemt naarmate t toeneemt.

the pocket cube

Pocket cube in a scrambled state. Mike Gonzalez (TheCoffee)

het bestuderen van het scrambling probleem voor de standaard 3x3x3 Rubik ‘ S Cube is momenteel een fascinerende onopgeloste uitdaging. Echter, het wordt heel beheersbaar als we onze aandacht richten op een kleinere 2x2x2 versie, genaamd de pocket cube.

In deze kubus zijn de rand-en middenstukken afwezig en blijven alleen de hoekdelen over. De Pocket cube heeft slechts 3.674.160 mogelijke toestanden, en zijn God ‘ S nummer is slechts 11.

in de grafiek hieronder zetten we d(t) uit voor de Pocket cube. Na 11 zetten is d(t) nog steeds erg groot, op 0,695. De eerste waarde van t die een d(t) waarde lager dan 0,25 oplevert (vaak “de mengtijd” genoemd in de Markov ketentheorie) is 19. Na 25 zetten is d(t) 0,092; na 50 zetten is het 0,0012; en na 100 zetten is het 0,00000017.

afstand van de verdeling van de Pocket cube van uniform na t-bewegingen. Eric Zhou

dus hoeveel zetten moet je gebruiken om een pocket cube volledig te versleutelen? Het antwoord hangt af van hoe klein je wilt dat d(t) is. Het is echter zeker waar dat Gods aantal bewegingen onvoldoende is. Als een absoluut minimum, moet men niet minder dan 19 zetten gebruiken. Meer details, waaronder code om d(t) te berekenen, zijn hier beschikbaar.

en natuurlijk, als je eenmaal je kubus hebt versleuteld, is alles wat je nog moet doen het opnieuw oplossen.

Geef een antwoord

Het e-mailadres wordt niet gepubliceerd. Vereiste velden zijn gemarkeerd met *