Hvor svært er det at scramble Rubiks terning?

Rubik ‘ s Cube har været et af verdens foretrukne puslespil i 40 år. Flere forskellige metoder er blevet udtænkt til at løse det, som forklaret i utallige bøger. Ekspert” speedcubers ” kan løse det i løbet af få sekunder.

ud over sådanne bedrifter med forbløffende fingerfærdighed er der mange fascinerende matematiske spørgsmål relateret til Rubiks terning. En bevægelse af terningen består i at dreje en af de seks ansigter med enten 90, 180 eller 270 grader. En svimlende 43.252.003.274.489.856.000 mulige tilstande kan opnås ved at anvende sekvenser af bevægelser til den løste tilstand.

På trods af denne kompleksitet blev det vist i 2010, at Rubiks terning altid kan løses i 20 bevægelser eller færre, uanset den oprindelige tilstand. Dette tal kaldes “Guds nummer”, da alle kendte løsningsmetoder, der anvendes af mennesker, typisk bruger betydeligt flere bevægelser end denne optimale værdi.

Rubiks terning i løst tilstand. (TheCoffee)

men hvad med det modsatte spørgsmål: hvor mange træk kræves for at scramble en løst terning? Ved første øjekast lyder dette som et meget lettere spørgsmål end at beregne Guds nummer. Trods alt, i modsætning til at løse en terning, scrambling man tager ingen dygtighed overhovedet.

lignende spørgsmål er blevet besvaret med succes for kortblanding. Et berømt eksempel er 1990-undersøgelsen af” riffle shuffle ” af matematikere Dave Bayer og Perci Diaconis. Et spil kort defineres som” blandet”, hvis ordren er tilfældig, hvor hver mulig ordre har samme sandsynlighed for at blive vist. Bayer og Diaconis viste, at syv riffelblandinger er nødvendige og tilstrækkelige til omtrent at blande et standarddæk med spillekort.

sidste år offentliggjorde matematikere en lignende undersøgelse af 15-puslespillet, som består af en 4H4-firkant fyldt med 15 glidende fliser og et tomt rum.

hvad betyder det for en terning at blive krypteret?

en typisk person, der forsøger at scramble en Rubiks terning, ville gentagne gange udføre tilfældige træk på den. Den resulterende tilfældige sekvens af stater er et specielt tilfælde af, hvad matematikere kalder en Markov-kæde. Nøgleegenskaben er, at i betragtning af den aktuelle tilstand afhænger sandsynligheden for, hvad den næste tilstand vil være, ikke af nogen af de tidligere stater.

anvendelse af teorien om Markov-Kæder til cube scrambling følger det, at når antallet af tilfældige bevægelser stiger, bliver sandsynligheden for at være i en bestemt af de mulige tilstande tættere og tættere på 1/43,252,003,274,489,856,000. Matematikere kalder dette en “ensartet sandsynlighedsfordeling”, da hver mulig tilstand forekommer med samme sandsynlighed.

efter et givet antal tilfældige bevægelser vil kubens tilstand være tilfældig, men dens sandsynlighedsfordeling vil ikke være nøjagtigt ensartet; nogle stater vil være mere tilbøjelige til at forekomme end andre.

lad d (t) beskrive, hvor meget sandsynlighedsfordelingen efter t tilfældige bevægelser adskiller sig fra den ensartede sandsynlighedsfordeling. Når antallet af tilfældige bevægelser(t) stiger, vil værdien af d (t) falde. Terningen, der krypteres, svarer til, at d (t) er lille.

Markov-kæde Monte Carlo

i teorien om Markov-kæder kaldes dette fald i d(t) “blanding”. Udover kortblanding og puslespil scrambling, teorien om Markov kæde blanding har også meget alvorlige praktiske anvendelser. Et af de vigtigste beregningsværktøjer inden for moderne videnskab og teknik er Monte Carlo-metoden. Denne metode, som det berømte casino, hvorefter det er navngivet, er grundlæggende afhængig af chance. I det væsentlige forsøger den at løse hårde matematiske problemer ved hjælp af flere tilfældige gæt.

i praksis bruges Markov-kæder ofte til at producere disse tilfældige tilstande. For at forstå nøjagtigheden af disse Markov-kæde Monte Carlo-metoder er nøgleopgaven at estimere, hvor hurtigt d(t) falder, når t stiger.

lommekuben

Lommekube i krypteret tilstand. (TheCoffee)

undersøgelse af scrambling problem for standard 3h3h3 Rubiks terning er i øjeblikket en fascinerende uløst udfordring. Det bliver dog ret håndterbart, hvis vi gør opmærksom på en mindre 2h2h2 version, kaldet pocket cube.

i denne terning er kant-og midterstykkerne fraværende, og kun hjørnestykkerne er tilbage. Lommekuben har kun 3.674.160 mulige stater, og dens Guds nummer er kun 11.

i grafen nedenfor tegner vi d(t) til lommekuben. Efter 11 træk er d (t) stadig meget stor ved 0,695. Den første værdi af t, der giver en d (t) værdi under 0,25 (ofte kaldet “blandetiden” i Markov-kædeteori) er 19. Efter 25 træk er d (t) 0,092; efter 50 træk er det 0,0012; og efter 100 træk er det 0.00000017.

afstand af lommekubefordelingen fra uniform efter t-bevægelser. Eric er

så hvor mange træk skal du bruge til fuldt ud at scramble en lommekube? Svaret afhænger af, hvor lille du gerne vil have d(t) at være. Men det er helt sikkert rigtigt, at Guds antal bevægelser er utilstrækkelig. Som et absolut minimum bør man ikke bruge færre end 19 Bevægelser. Yderligere oplysninger, herunder kode til beregning af d (t), er tilgængelige her.

og selvfølgelig, når du har scrambled din terning, er alt, hvad der er tilbage at gøre, at løse det igen.

Skriv et svar

Din e-mailadresse vil ikke blive publiceret. Krævede felter er markeret med *