Hvor vanskelig er Det Å rykke Ut Rubiks Kube?

Rubiks Kube Har vært en av verdens favoritt puslespill for 40 år. Flere forskjellige metoder har blitt utviklet for å løse det, som forklart i utallige bøker. Ekspert «speedcubers» kan løse det om noen sekunder.I tillegg til slike prestasjoner av forbløffende fingerferdighet, er det mange fascinerende matematiske spørsmål knyttet Til Rubiks Kube. Et trekk av kuben består av å rotere en av de seks ansiktene med enten 90, 180 eller 270 grader. En svimlende 43,252,003,274,489,856,000 mulige tilstander kan oppnås ved å bruke sekvenser av trekk til løst tilstand. Til tross for denne kompleksiteten ble Det vist i 2010 At Rubiks Kube alltid kan løses i 20 trekk eller færre, uavhengig av opprinnelig tilstand. Dette tallet refereres til Som «Guds tall», da alle kjente løsningsmetoder som brukes av mennesker, vanligvis bruker betydelig flere trekk enn denne optimale verdien.

Rubiks Kube i løst tilstand. Mike Gonzalez (TheCoffee)

men hva med det motsatte spørsmålet: hvor mange trekk kreves for å kryptere en løst kube? Ved første øyekast høres dette ut som et mye enklere spørsmål enn å beregne Guds nummer. Tross alt, i motsetning til å løse en kube, scrambling man tar ingen ferdighet overhodet.

Lignende spørsmål har blitt besvart vellykket for kort shuffling. Et kjent eksempel er 1990-studien av «riffle shuffle» av matematikere Dave Bayer og Perci Diaconis. En kortstokk er definert som» blandet » hvis bestillingen er tilfeldig, med hver mulig ordre som har samme sannsynlighet for å vises. Bayer og Diaconis viste at syv riffle shuffles er nodvendige og tilstrekkelige for a omtrent blande en standard dekk med spillkort.

i fjor publiserte matematikere en lignende studie av 15-puslespillet, som består av en 4×4-firkant fylt med 15 glidende fliser og en tom plass.

hva betyr det for en kube å bli kryptert?

en typisk person som prøver Å rykke Ut En Rubiks Kube ville gjentatte ganger utføre tilfeldige trekk på den. Den resulterende tilfeldige sekvensen av stater er et spesielt tilfelle av hva matematikere kaller En Markov-kjede. Nøkkelegenskapen er at gitt den nåværende tilstanden, er sannsynligheten for hva neste stat vil være, ikke avhengig av noen av de tidligere statene.

Ved Å Bruke Teorien Om Markov-kjeder til kube scrambling, følger det at når antall tilfeldige trekk øker, blir sannsynligheten for å være i en bestemt av de mulige tilstandene nærmere og nærmere 1/43,252,003,274,489,856,000. Matematikere kaller dette en «jevn sannsynlighetsfordeling», da hver mulig tilstand oppstår med samme sannsynlighet.

etter et gitt antall tilfeldige trekk vil tilstanden til kuben være tilfeldig, men sannsynlighetsfordelingen vil ikke være nøyaktig ensartet; noen tilstander vil være mer sannsynlig å forekomme enn andre.

La d (t) beskrive hvor mye sannsynlighetsfordelingen etter t tilfeldige trekk avviker fra den ensartede sannsynlighetsfordelingen. Etter hvert som antall tilfeldige trekk (t) øker, vil verdien av d(t) reduseres. Kuben som krypteres tilsvarer at d (t) er liten.

Markov-kjede Monte Carlo

i teorien Om Markov-kjeder kalles denne nedgangen i d(t) «blanding». Foruten kort shuffling og puslespill scrambling, teorien Om Markov kjeden blanding har også svært alvorlige praktiske anvendelser. Et av De viktigste beregningsverktøyene i moderne vitenskap og ingeniørfag er Monte Carlo-metoden. Denne metoden, som det berømte kasinoet som det heter, er avhengig av sjanse. I hovedsak forsøker den å løse vanskelige matematiske problemer ved hjelp av flere tilfeldige gjetninger.

I praksis Brukes Markov-kjeder ofte til å produsere disse tilfeldige tilstandene. For å forstå nøyaktigheten av Disse Markov-kjeden Monte Carlo-metodene, er hovedoppgaven å anslå hvor raskt d (t) reduseres etter hvert som t øker.

lommekuben

Lommekube i kryptert tilstand. Mike Gonzalez (TheCoffee)

Å Studere scrambling problemet for standard 3x3x3 Rubiks Kube er for tiden en fascinerende uløst utfordring. Det blir imidlertid ganske overkommelig hvis vi gjør oppmerksomheten til en mindre 2x2x2-versjon, kalt pocket cube.

i denne kuben er kant-og midtstykkene fraværende, og bare hjørnestykkene forblir. Pocket cube har bare 3.674.160 mulige stater, Og Guds nummer er bare 11.

i grafen nedenfor plotter vi d (t) for lommekuben. Etter 11 trekk er d (t) fortsatt veldig stor, ved 0.695. Den første verdien av t som gir en d (t) verdi under 0,25 (ofte kalt «blandetiden» I Markov kjedeteori) er 19. Etter 25 trekk er d (t) 0,092; etter 50 trekk er det 0,0012; og etter 100 trekk er det 0.00000017.

Avstand av lommekubefordelingen fra uniform etter t-trekk. Eric Zhou

så hvor mange trekk bør du bruke til å rykke ut en lommekube? Svaret avhenger av hvor liten du vil at d (t) skal være. Men Det er sikkert sant At Guds antall trekk er utilstrekkelig. Som et minimum bør man ikke bruke færre enn 19 trekk. Ytterligere detaljer, inkludert kode for a beregne d (t), er tilgjengelige her.Og selvfølgelig, når du har kryptert kuben din, er alt som er igjen å gjøre, å løse det igjen.

Legg igjen en kommentar

Din e-postadresse vil ikke bli publisert. Obligatoriske felt er merket med *