Videnskab
 science >> Videnskab >  >> Andet

Hvor svært er det at scramble Rubiks Cube?

Rubiks terning i den løste tilstand. Kredit:Mike Gonzalez (TheCoffee)

Rubik's Cube har været et af verdens foretrukne gåder i 40 år. Der er udtænkt flere forskellige metoder til at løse det, som forklaret i utallige bøger. Ekspert "speedcubers" kan løse det på få sekunder.

Ud over sådanne bedrifter af forbløffende fingerfærdighed, der er mange fascinerende matematiske spørgsmål relateret til Rubiks terning. En bevægelse af terningen består af at rotere en af ​​de seks flader 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 træk til den løste tilstand.

På trods af denne kompleksitet, det blev vist i 2010, at Rubiks terning altid kan løses i 20 træk eller færre, uanset starttilstanden. Dette nummer omtales som "Guds nummer, ", da alle kendte løsningsmetoder, der bruges af mennesker, typisk bruger betydeligt flere bevægelser end denne optimale værdi.

Men hvad med det modsatte spørgsmål:hvor mange træk kræves der for at kryptere en løst terning? Ved første øjekast, det lyder som et meget nemmere spørgsmål end at beregne Guds tal. Trods alt, i modsætning til at løse en terning, det kræver ingen evner overhovedet.

Lignende spørgsmål er blevet besvaret med succes for kortblanding. Et berømt eksempel er undersøgelsen fra 1990 af "riffle shuffle" af matematikerne Dave Bayer og Perci Diaconis. Et sæt kort er defineret som "blandet", hvis rækkefølgen er tilfældig, med hver mulig rækkefølge har samme sandsynlighed for at dukke op. Bayer og Diaconis viste, at syv riffle-shuffles er nødvendige og tilstrækkelige til omtrent at blande et standardspil med spillekort.

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

Lommeterning i krypteret tilstand. Kredit:Mike Gonzalez (TheCoffee)

Hvad betyder det, at en terning bliver forvrænget?

En typisk person, der forsøger at kryptere en Rubik's Cube, ville gentagne gange udføre tilfældige bevægelser på den. Den resulterende tilfældige sekvens af tilstande er et specialtilfælde af, hvad matematikere kalder en Markov-kæde. Nøgleegenskaben er, at givet den nuværende tilstand, sandsynligheden for, hvad den næste tilstand vil være, afhænger ikke af nogen af ​​de tidligere tilstande.

Anvendelse af teorien om Markov-kæder til terningforvrængning, det følger, at når antallet af tilfældige træk stiger, sandsynligheden for at være i en bestemt af de mulige tilstande bliver tættere og tættere på 1/43, 252, 003, 274, 489, 856, 000. Matematikere kalder dette en "ensartet sandsynlighedsfordeling, ", da hver mulig tilstand opstår med samme sandsynlighed.

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

Lade d(t) beskriv hvor meget sandsynlighedsfordelingen efter t tilfældige træk adskiller sig fra den ensartede sandsynlighedsfordeling. Som antallet af tilfældige træk ( t ) stiger, værdien af d(t) vil falde. Terningen, der forvrænges, svarer til d(t) at være lille.

Markov-kæden Monte Carlo

I teorien om Markov-kæder, dette fald i d(t) kaldes "blanding". Udover kortblanding og puslespil, teorien om Markov-kædeblanding har også meget seriøse praktiske anvendelser. Et af de vigtigste beregningsværktøjer i moderne videnskab og teknik er Monte Carlo-metoden. Denne metode, som det berømte kasino, som det er opkaldt efter, baserer sig grundlæggende på tilfældigheder. I det væsentlige, den forsøger tilnærmelsesvis at løse svære matematiske problemer ved hjælp af flere tilfældige gæt.

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

Lommeterningen

At studere scrambling-problemet for standard 3x3x3 Rubik's Cube er i øjeblikket en fascinerende uløst udfordring. Imidlertid, det bliver ret overskueligt, hvis vi vender vores opmærksomhed mod en mindre 2x2x2 version, kaldet lommeterningen.

I denne terning, kant- og midterstykkerne mangler, og kun hjørnestykkerne er tilbage. Lommeterningen har kun 3, 674, 160 mulige tilstande, og Guds tal er kun 11.

I grafen nedenfor, vi plotter d(t) til lommeterningen. Efter 11 træk, d(t) er 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 "blandingstiden" i Markov-kædeteorien) er 19. Efter 25 træk d(t) er 0,092; efter 50 træk er det 0,0012; og efter 100 træk er det 0,00000017.

Afstand af lommeterningfordelingen fra uniform efter t bevæger sig. Kredit:Eric Zhou

Så hvor mange træk skal du bruge for at kryptere en lommeterning fuldt ud? Svaret afhænger af, hvor lille du gerne vil have d(t) at være. Imidlertid, det er bestemt rigtigt, at Guds antal træk er utilstrækkeligt. Som et absolut minimum, man bør ikke bruge færre end 19 træk. Flere detaljer, inklusive kode til at beregne d(t) , findes her.

Og selvfølgelig, når du har forvrænget din terning, det eneste, der er tilbage at gøre, er at løse det igen.

Denne artikel er genudgivet fra The Conversation under en Creative Commons-licens. Læs den originale artikel.




Varme artikler