Mennyire nehéz a Rubik-kockát összekeverni?

Rubik kockája 40 éve a világ egyik kedvenc rejtvénye. Számos különböző módszert dolgoztak ki annak megoldására, amint azt számtalan könyv magyarázza. A “speedcubers” szakértő másodpercek alatt megoldhatja.

a meghökkentő ügyesség ilyen bravúrjai mellett számos lenyűgöző matematikai kérdés merül fel Rubik kockájával kapcsolatban. A kocka mozgatása a hat arc egyikének 90, 180 vagy 270 fokkal történő elforgatásából áll. A megdöbbentő 43,252,003,274,489,856,000 lehetséges állapotokat lehet beszerezni alkalmazásával sorozatok mozog a megoldott állapot.

ennek a bonyolultságnak ellenére 2010-ben kimutatták, hogy a Rubik-kocka mindig 20 mozdulattal vagy kevesebbel megoldható, függetlenül a kezdeti állapottól. Ezt a számot “Isten számának” nevezik, mivel az emberek által használt összes ismert megoldási módszer általában lényegesen több mozdulatot használ, mint ez az optimális érték.

Rubik-kocka megoldott állapotban. Mike Gonzalez (TheCoffee)

de mi a helyzet az ellenkező kérdéssel: hány mozdulatra van szükség a megoldott kocka összekeveréséhez? Első pillantásra ez sokkal könnyebb kérdésnek hangzik, mint Isten számának kiszámítása. Végül is, ellentétben a kocka megoldásával, a rejtjelezés nem vesz semmilyen készséget.

hasonló kérdésekre sikeresen válaszoltak a kártya keveréséhez. Híres példa erre Dave Bayer és Perci Diaconis matematikusok “riffle shuffle” című 1990-es tanulmánya. A kártyacsomag meghatározása “vegyes”, ha a megrendelés Véletlenszerű, minden lehetséges megrendelés azonos valószínűséggel jelenik meg. Bayer és Diaconis megmutatta, hogy hét riffle shuffle szükséges és elegendő ahhoz, hogy megközelítőleg összekeverjük a standard pakli játékkártya.

tavaly a matematikusok hasonló tanulmányt tettek közzé a 15 puzzle-ről, amely egy 4×4 négyzetből áll, tele 15 csúszó csempével és egy üres térrel.

mit jelent egy kocka kódolása?

egy tipikus ember, aki megpróbál egy Rubik-kockát összekeverni, többször véletlenszerű mozdulatokat hajt végre rajta. Az így kapott véletlenszerű állapotsor különleges eset, amit a matematikusok Markov Láncnak neveznek. A legfontosabb tulajdonság az, hogy a jelenlegi állapot miatt a következő állapot valószínűsége nem függ a korábbi állapotoktól.

A Markov-láncok elméletének alkalmazása a kocka-kódolásra, ebből következik, hogy a véletlenszerű mozgások számának növekedésével a lehetséges állapotok bármelyikének valószínűsége egyre közelebb kerül 1/43,252,003,274,489,856,000. A matematikusok ezt “egységes valószínűségi eloszlásnak” nevezik, mivel minden lehetséges állapot azonos valószínűséggel fordul elő.

bármely adott számú véletlenszerű lépés után a kocka állapota véletlenszerű lesz, de valószínűségi eloszlása nem lesz pontosan egységes; egyes államok nagyobb valószínűséggel fordulnak elő, mint mások.

let d(t) írja le, hogy a valószínűségi eloszlás a T véletlenszerű mozdulatok után mennyire különbözik az egységes valószínűségi eloszlástól. Ahogy a véletlenszerű mozgások (t) száma növekszik, a d(t) értéke csökken. A kódolt kocka annak felel meg, hogy D(t) kicsi.

Markov-lánc Monte Carlo

A Markov-láncok elméletében ezt a d(t) csökkenést “keverésnek”nevezik. A kártyacsomag és a puzzle-rejtjelezés mellett a Markov-lánc keverésének elmélete is nagyon komoly gyakorlati alkalmazásokkal rendelkezik. A modern tudomány és technika egyik legfontosabb számítási eszköze a Monte Carlo-módszer. Ez a módszer, mint a híres kaszinó, amely után nevezték, alapvetően a véletlenre támaszkodik. Lényegében megpróbálja megközelítőleg megoldani a nehéz matematikai problémákat több véletlenszerű találgatás segítségével.

a gyakorlatban a Markov láncokat gyakran használják ezeknek a véletlenszerű állapotoknak a előállítására. A Markov-lánc Monte Carlo módszereinek pontosságának megértése érdekében a legfontosabb feladat annak becslése, hogy a d(t) milyen gyorsan csökken a t növekedésével.

the pocket cube

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

a 3x3x3 Rubik-kocka rejtjelezési problémájának tanulmányozása jelenleg lenyűgöző megoldatlan kihívás. Azonban nagyon kezelhetővé válik, ha figyelmünket egy kisebb 2x2x2-es verzióra fordítjuk, amelyet pocket cube-nak hívnak.

ebben a kockában az él és a középső darabok hiányoznak, és csak a sarokdarabok maradnak meg. A zsebkocka csak 3,674,160 lehetséges állapotokkal rendelkezik, Isten száma pedig csak 11.

az alábbi grafikonon D(t) – T ábrázolunk a zsebkocka számára. 11 lépés után a d (t) még mindig nagyon nagy, 0,695-nél. A T első értéke, amely d(t) értéket ad 0, 25 alatt (a Markov-láncelméletben gyakran “keverési időnek” nevezik), 19. 25 lépés után a d(t) 0,092; 50 lépés után 0,0012; 100 lépés után pedig 0,00000017.

a zsebkocka eloszlásának távolsága az egyenruha után t mozog. Eric Zhou

tehát hány mozdulatot kell használni a zsebkocka teljes keveréséhez? A válasz attól függ, hogy milyen kicsi szeretne d (t) lenni. Azonban minden bizonnyal igaz, hogy Isten mozdulatainak száma nem elegendő. Minimumként nem szabad kevesebb, mint 19 mozdulatot használni. További részletek, beleértve a d(t) számítási kódot, itt érhetők el.

és természetesen, ha egyszer már rántotta a kocka, csak annyit kell tennie, hogy megoldja újra.

Vélemény, hozzászólás?

Az e-mail-címet nem tesszük közzé. A kötelező mezőket * karakterrel jelöltük