Jak těžké je prorazit Rubikovu kostku?

Rubikova kostka je jednou z nejoblíbenějších hádanek na světě již 40 let. Pro jeho řešení bylo navrženo několik různých metod, jak je vysvětleno v nesčetných knihách. Expert „speedcubers“ to může vyřešit během několika sekund.

kromě takových výkonů ohromující obratnosti existuje mnoho fascinujících matematických otázek souvisejících s Rubikovou kostkou. Pohyb krychle se skládá z otáčení jedné ze šesti ploch o 90, 180 nebo 270 stupňů. Ohromující 43,252,003,274,489,856,000 možné stavy lze získat aplikací sekvencí tahů na řešený stav.

navzdory této složitosti se v roce 2010 ukázalo, že Rubikova kostka může být vždy vyřešena 20 pohyby nebo méně, bez ohledu na počáteční stav. Toto číslo je označováno jako „Boží číslo“, protože všechny známé metody řešení používané lidmi obvykle používají podstatně více pohybů než tato optimální hodnota.

Rubikova Kostka v řešené státu. Mike Gonzalez (TheCoffee)

Ale to, co o opačnou otázku: kolik tahů jsou nutné k rušení vyřešil kostku? Na první pohled to zní jako mnohem jednodušší otázka než výpočet Božího čísla. Koneckonců, na rozdíl od řešení krychle, míchání člověk nemá žádnou dovednost vůbec.

podobné otázky byly úspěšně zodpovězeny pro míchání karet. Slavným příkladem je studie „riffle shuffle“ z roku 1990 matematiky Dave Bayer a Perci Diaconis. Balíček karet je definován jako „smíšený“, pokud je jeho pořadí Náhodné, přičemž každá možná objednávka má stejnou pravděpodobnost, že se objeví. Bayer a Diaconis ukázaly, že sedm riffle shuffles jsou nezbytné a dostatečné přibližně míchat standardní balíček hracích karet.

v loňském roce publikovali matematici podobnou studii 15 puzzle, která se skládá z čtverce 4×4 naplněného 15 posuvnými dlaždicemi a jedním prázdným prostorem.

co to znamená pro kostku, která má být kódována?

typický člověk, který se snaží vyškrábat Rubikovu kostku, by na ní opakovaně prováděl náhodné pohyby. Výsledná náhodná posloupnost stavů je zvláštním případem toho, co matematici nazývají markovským řetězcem. Klíčovou vlastností je, že vzhledem k současnému stavu pravděpodobnost, jaký bude další stav, nezávisí na žádném z předchozích států.

Použití teorie Markovových řetězců, aby kostku míchat, z toho vyplývá, že jak počet náhodných tahů, zvyšuje se pravděpodobnost, že v určitém jeden z možných stavů se stává blíž a blíž k 1/43,252,003,274,489,856,000. Matematici to nazývají „rovnoměrným rozdělením pravděpodobnosti“, protože každý možný stav nastává se stejnou pravděpodobností.

po daném počtu náhodných pohybů bude stav krychle náhodný, ale jeho rozdělení pravděpodobnosti nebude přesně jednotné; některé stavy budou pravděpodobnější než jiné.

Nechť d(t) popsat, jak moc se rozdělení pravděpodobnosti po t náhodné pohyby se liší od rovnoměrné rozdělení pravděpodobnosti. Jak se počet náhodných pohybů (t) zvyšuje, hodnota d (t) se sníží. Míchaná krychle odpovídá tomu, že D(t) je malá.

Markovův řetězec Monte Carlo

v teorii markovských řetězců se tento pokles d (t) nazývá „míchání“. Kromě míchání karet a skládání hádanek má teorie Markovova míchání řetězců také velmi vážné praktické aplikace. Jedním z nejdůležitějších výpočetních nástrojů v moderní vědě a inženýrství je metoda Monte Carlo. Tato metoda, stejně jako slavné kasino, po kterém je pojmenováno, se zásadně spoléhá na náhodu. V podstatě se pokouší přibližně řešit těžké matematické problémy pomocí několika náhodných odhadů.

v praxi se Markovské řetězce často používají k výrobě těchto náhodných stavů. Pochopit správnost těchto Markov-chain Monte Carlo metody, klíčovým úkolem je odhadnout, jak rychle se d(t) klesá t zvyšuje.

kapesní krychle

Kapesní krychle v kódovaném stavu. Mike Gonzalez (TheCoffee)

Studium zakódování problém pro standardní 3x3x3 Rubikova Kostka je v současné době fascinující nevyřešený výzvou. Stává se však docela zvládnutelné, pokud obrátíme pozornost na menší verzi 2x2x2, nazvanou pocket cube.

v této krychli chybí okrajové a středové kusy a zůstávají pouze rohové kusy. Kapesní kostka má pouze 3 674 160 možných stavů a její Boží číslo je pouze 11.

v grafu níže vykreslíme d (t) pro kapesní kostku. Po 11 tahech je d (t) stále velmi velký, na 0, 695. První hodnota t, která dává hodnotu d (t) pod 0,25 (často nazývaná „doba míchání“ v markovově teorii řetězců), je 19. Po 25 tahů d(t) je 0.092; po 50 tahů je 0.0012; a po 100 pohybech je to 0,00000017.

Vzdálenost kapsy cube distribuce z jednotné po t se pohybuje. Eric Zhou

Tak kolik se pohybuje byste měli použít, aby plně scramble kapesní krychle? Odpověď závisí na tom, jak malý byste chtěli d (t)být. Je však jistě pravda, že Boží počet tahů je nedostatečný. Jako holé minimum by člověk neměl používat méně než 19 tahů. Další podrobnosti, včetně kódu pro výpočet d (t), jsou k dispozici zde.

a samozřejmě, jakmile jste míchaná kostku, vše, co zbývá udělat, je vyřešit znovu.

Napsat komentář

Vaše e-mailová adresa nebude zveřejněna. Vyžadované informace jsou označeny *