Počet kombinací Rubikovy kostky NxNxN
Mějme Rubikovu kostku NxNxN, kde N značí počet vrstev. Jistě mi dáte za pravdu, že při porovnání dvou kostek s různým N je složitější ta s vyšším N (kostka 5x5x5 je složitější než 2x2x2). Alespoň časově. Proč tomu tak je?
Je to proto, že kostka s vyšším N má více pohyblivých dílků, což má za následek větší počet kombinací, které na kostce můžou nastat. Je to přímá úměra - čím více dílků, tím více kombinací, tím delší časový horizont potřebujeme ke složení.
Pro počet kombinací na Rubikově kostce NxNxN dokonce existuje několik tvarů vzorečku. K takovému tvaru, který je prezentován právě na této stránce, mě doslova dokopal Michael Gottlieb, za což mu patří velký dík. Rovnici jsem s ním několikrát diskutoval.
Počet kombinací, které na Rubikově kostce NxNxN mohou nastat, je roven
 |
kde N udává počet vrstev, vykřičník představuje faktoriál a mod je modulo. Modulo je matematická operace - více o ní se dá najít třeba na wikipedii. Pro naše účely postačí informace, že exponent první závorky zleva nabývá pouze hodnot 0 nebo 1. Pokud je N sudé číslo, je exponent 0. Pakliže je N liché číslo, je exponent 1. Je třeba upozornit na to, že rovnice neobsahuje hranaté závorky. To, co se na první pohled může zdát jako hranatá závorka v exponentu, je ve skutečnosti dolní celá část čísla (všimněte si, že chybí i horní "zobáček" závorky). Dolní celá část čísla je opět popsána např. ve wikipedii. Jednoduše řečeno jde o číslo, které se nachází před desetinnou čárkou. Čísla desetinnou čárku neobsahující (označme je X) si lze představit např. ve tvaru X,00. Pak je dolní celá část rovna X.
Je nutno podotknout, že vzorec platí pro N > 1. Naštěstí pro N = 1 nemusíme nic počítat, protože Rubikova kostka 1x1x1 má jen jednu možnou kombinaci.
Možná si řeknete: "no jo, ale počínaje kostkou 4x4x4 jsou středy složeny z několika dílků. Tyto středové dílky se rovněž mohou mezi sebou přesouvat (permutovat), takže počet celkových kombinací bude větší". Máte pravdu, ale jen jako v ruské pohádce - čili částečnou. Středové kostičky pro "větší" kostky (pro N > 3) se opravdu vzájemně mohou přesouvat, my to však nemusíme zaznamenat. Pro nás se středové kostičky jedné barvy jeví jedna jako druhá, tudíž je zkrátka nerozeznáme. Jsou pro nás identické.
Ledaže bychom středové kostičky udělali vzájemně odlišitelné. Pokud na středy kostky namalujete obrázek, který bude složen jen v jedné kombinaci kostiček, vznikne vám Supercube. Pro Supercube existuje modifikovaný vzorec, jenž uvádí např. Chris Hardwick. Čím více dílků na Rubikově kostce dokážeme vzájemně rozlišit, tím větší bude počet kombinací hlavolamu.
Pro vzorec napsaný výše jsem sestavil jednoduchou online kalkulačku. Stačí na začátku zapisovacího řádku přepsat hodnotu N ve "for N=3". Defaultně je tudíž kalkulačka nastavena na N = 3.
Ken Silverman je autorem simulátoru Rubikovy kostky 1x1x1 - 256x256x256. Teoreticky ještě větší kostky se dají skládat např. na aplikaci IsoCubeSim (autorem je Michael Gottlieb a nabízí i kostky LxMxN). Mně osobně se víc líbí simulátor Rubix (kostky 2x2x2 - 50x50x50), jehož autorem je Peter Bone. Nabízí sice menší rozměry kostky, ale pro běžného smrtelníka jsou pořád dostačující. Navíc, a to především, se mi v tomto simulátoru s kostkou lépe manipuluje myší. Ale to je asi jen o zvyku.
Pojďme si nyní vzorec uvedený výše odvodit (kdyžtak přeskočte - odvození končí modrým nápisem "Rubikova kostka 1x1x1"). K tomu, abychom mohli začít, je nejprve nutné si uvědomit, jaké dílky vlastně do rovnice zahrneme. Rubikova kostka 3x3x3 se skládá ze tří typů dílků: středy, hrany a rohy. Rubikova kostka 5x5x5 už má ale dílků více.
Musíme tak brát v úvahu následující dílky: pevné středy, pohyblivé středy, centrální hrany, křídelní hrany a rohy.
|
| Obr. 1 - Typy dílků Rubikovy kostky 7x7x7 a znázornění kompozitní hrany |
Na obr. 1 je graficky ilustrována jedna vnější vrstva Rubikovy kostky 7x7x7. Černě je vykreslen pevný střed, žlutě, šedě a oranžově jsou vyobrazeny pohyblivé středy, červeně jsou nakresleny centrální hrany, modře jsou namalovány křídelní hrany a konečně zeleně jsou zobrazeny rohy hlavolamu.
Možná se ptáte, proč mají pohyblivé středy tři barvy? Je to z toho důvodu, že se jedná o tři typy na sobě nezávislých dílků. Stejně tak jako nemůžete zaměnit roh s (centrální) hranou na Rubikově kostce 3x3x3, nemůžete zaměnit ani žluté se šedými nebo oranžovými pohyblivými dílky. Žlutým pohyblivým středům se říká "+středy" (spolu s pevným středem formují znak "+"), kdežto šedým pohyblivým středům říkáme "X-středy" (spolu s pevným středem formují znak "X"), načež pro oranžové pohyblivé středy se vžilo pojmenování "kosoúhlé středy" (spolu s pevným středem tvoří kosý úhel). Pro další úvahy nebude zapotřebí tyto tři typy dílků vzájemně rozlišovat a souhrnně tak budou nazývány pohyblivé středy.
Dále je na obr. 1 možné pozorovat fialový komplet dílků. Útvar, který se skládá z křídelních hran a centrální hrany, a který sousedí s dvěma rohy, souhrnně nazýváme kompozitní hrana. Protože "sudé kostky" (N = sudé číslo) nemají centrální hrany, kompozitní hrana se u nich sestává pouze z křídelních hran. Naopak "liché kostky" (N = liché číslo) mají jak křídelní hrany, tak centrální hrany. Jedna kompozitní hrana se tak v případě Rubikovy kostky 4x4x4 skládá ze dvou křídelních hran, zatímco jednu kompozitní hranu v případě Rubikovy kostky 5x5x5 tvoří jedna centrální hrana a dvě křídelní hrany.
Představíme-li si kompozitní hranu jako letadlo, pak trup tvoří centrální hrana a křídelní hrany znázorňují křídla letadla - odtud pojmenování křídelní hrana (představa platí pro liché kostky, ale princip zůstává stejný i pro sudé kostky).
Pevný střed je takový, se kterým nemůžeme "pohnout" - zatímco pro liché kostky takové středy existují, na sudých kostkách tyto pevné středy nenajdeme.
Pohyblivé středy se nacházejí na všech kostkách pro N > 3. Např. pro Rubikovu kostku 4x4x4 označujeme jako pohyblivé středy vnitřní 4 dílky na jednotlivých stěnách kostky. Pro Rubikovu kostku 5x5x5 označujeme jako pohyblivé středy ty dílky, které tvoří vnitřní 3x3 pole mínus pevný střed v rámci jedné stěny. V případě kostky 5x5x5 tak jde o 8 dílků.
Centrální hrany mají stejné vlastnosti jako hrany u kostky 3x3x3 a najdeme je jen u lichých kostek.
Pro N > 1 se na kostce vyskytuje vždy 8 rohových dílků, zkráceně rohů.
Technicky vzato je výše uvedený vztah kombinací dvou vzorců - jednoho pro výpočet kombinací pro liché kostky a druhého pro výpočet kombinací sudých kostek. Aby oba tyto vzorce bylo možné vyjádřit jen jednou formulí, bylo nutné zvolit si jakýsi referenční bod, který bude určovat "pozici kostky". Jako referenční bod se může zvolit např. fixace pevných středů. To ale pro sudé kostky nelze učinit, protože pevný střed neobsahují. Proto za referenční bod byla zvolena fixace jednoho rohu kostek.
Po zafixování jednoho rohu se zbylé rohy mohou permutovat (přemisťovat, přesouvat, prohazovat) 7! způsoby, přičemž při fixní orientaci daného rohu může být zbylých 7 rohů orientováno 36 způsoby (jeden ze sedmi rohů se musí podřídit orientaci fixního rohu).
Pro liché kostky se při fixaci jednoho rohu můžou pevné středy permutovat - pokud se na pravé stěně nachází určitý střed, na levé stěně je jednoznačně dán střed opozitní. Zbylé 4 středy se tahem M dají permutovat a to 4 způsoby. Protože stěn je 6 (tzn. že do pravé stěny můžeme umístit 6 odlišných středů), je celkový počet permutací středů roven součinu 6·4. Orientace středů jsou vzájemně nerozeznatelné, tudíž existuje jen 1 případ => počet kombinací pro pevné středy je tak 6·4·1 = 24.
Pro liché kostky dále platí, že centrální hrany je možné orientovat 211 způsoby a permutovat 12!/2 způsoby (více viz značení tahů Rubikovy kostky). Čili 210·12! kombinací.
Pro to, aby tyto součiny byly uvažovány pro liché kostky, ale zároveň aby nebyly uvažovány pro sudé kostky (které nemají ani pevné středy ani centrální hrany), slouží operace modulo - konkrétně exponent N mod2.
Křídelní hrany mají 24! způsobů permutace ve své orbitě (oběžné dráze, ve které se mohou vyskytovat) a 1 způsob orientace => 24!·1 = 24! kombinací. Pro liché kostky existuje (N-3)/2 orbit, kdežto pro sudé kostky existuje (N-2)/2 orbit. Bez újmy na obecnosti lze tyto dva členy souhrnně zapsat jako dolní celá část ((N-2)/2).
V každé orbitě pohyblivých středů existuje 24!/(4!6) kombinací, protože každá orbita pohyblivých středů má na jedné stěně kostky (těch je celkem 6) 4 identické dílky. Jinými slovy řečeno v jedné orbitě pohyblivých středů je 24 dílků, přičemž na každé stěně kostky se nacházejí 4 z nich, které nejsou barevně rozlišitelné. Sudé kostky mají ((N-2)·(N-2))/4 = ((N-2)/2)2 orbit pohyblivých středů, kdežto liché kostky mají ((N-1)·(N-3))/4 = ((N-2)/2)2-1/4 takových orbit pohyblivých středů. Bez újmy na obecnosti lze tyto dva členy souhrnně zapsat jako dolní celá část (((N-2)/2)2).
Následuje krátký výčet několika kostek s rozdílným počtem vrstev. K nim jsou přidány časy, kterých nejrchychlejší kostkaři dosahují.
Rubikova kostka 1x1x1
Kostka má jen jednu pozici. Doba složení je kratší než desetina sekundy.
Rubikova kostka 2x2x2
Kostka má 3 674 160 kombinací (7 číslic). Doba složení je kratší než 2 sekundy.
Rubikova kostka 3x3x3
Počet kombinací kostky je roven číslu o 20 číslicích. Doba složení je kratší než 6 sekund.
Rubikova kostka 4x4x4
Počet kombinací kostky je roven číslu o 46 číslicích. Doba složení je kolem 20 sekund.
Rubikova kostka 5x5x5
Počet kombinací kostky je roven číslu o 75 číslicích. Doba složení je kolem 38 sekund.
Rubikova kostka 6x6x6
Počet kombinací kostky je roven číslu o 117 číslicích. Doba složení je kolem 1 minuty a 15 sekund.
Rubikova kostka 7x7x7
"Největší" kostka, s jakou se oficiálně soutěží. Počet kombinací je roven číslu o 161 číslicích. Doba složení je kolem 1 minuty a 50 sekund.
Rubikova kostka 20x20x20
Dvakrát v životě jsem si na počítači zkusil tohodle drobka složit. Poprvé mi to trvalo 20 hodin, podruhé něco málo přes 8 hodin (už jsem věděl jak na to a na co si dát při skládání pozor). Počet kombinací je roven číslu o 1 478 číslicích. Doba složení světového rekordu (samo. neoficiálního) je 53 minut a 10 sekund a tento čas má v držení Michael Gottlieb.
Rubikova kostka 33x33x33
Od roku 2017 největší reálná a plně funkční vyrobená kostka vůbec (nevyrábí se však sériově). Počet kombinací je roven číslu o 4 100 číslicích. Doba složení je dlouho.
Rubikova kostka 111x111x111
V květnu 2013 poskládal Michael Gottlieb takto velkou kostku za necelých 30 hodin čistého času (29 hodin, 52 minut a 2.64 sekund). Počet kombinací kostky je roven číslu o 47 374 číslicích. Kostka byla složena za pomoci modifikace metody Cage.
Rubikova kostka 121x121x121
V září 2013 tohoto obříka poskládal Adrian Acosta za 89 hodin, 2 minuty a 2.26 sekund čistého času a celkově na svůj pokus spotřeboval 2 106 hodin (tj. zhruba 3 měsíce). Počet kombinací je roven číslu o 56 334 číslicích. Ke skládání použil metodu nejdřív středy, poté hrany (samozřejmě byla metoda dost optimalizována, i přesto potřeboval ke složení kostky 623 523 tahů).
Rubikova kostka 128x128x128
V listopadu 2014 potřeboval Michael Gottlieb 26 hodin, 25 minut a 19 sekund na složení tohoto hlavolamu. Musel poskládat celkem 96 776 kostiček / dílků a to dokázal jen pomocí 157 318 tahů!!! Obdivuhodný je i jeho poměr počtu tahů na 1 sekundu - činí 1.65! Počet možných kombinací na tomhle gigantu je číslo o 63 071 číslicích. Michael, stejně tak jako v případě svého pokusu na kostce 111x111x111, použil modifikovanou / optimalizovanou metodu Cage.
Rubikova kostka 150x150x150
Největší kostka složená člověkem. Šest minut po desáté hodině dne 16. 2. 2020 viděl Ben Whitmore před sebou na monitoru něco takovéhoto:
 |
Za 21 dnů, 16 hodin a 1 minutu později už měl hlavolam složený. Neskládal však non-stop, ale jen v 8.2 % tohoto období. Čistý čas použitý na složení tudíž představuje pouze 42 hodin, 40 minut a 28 sekund! Podobně jako předešlý rekordman Michael Gottlieb, i Ben použil ve svém pokusu modifikovanou / optimalizovanou metodu Cage. Následuje výčet některých dalších statistik:
Počet tahů: 239 283
Počet tahů za sekundu: 1.558 (!!!)
Počet rotací kostky: 76 458
Počet dílků / kostiček: 133 208
Počet kombinací: číslo o 86 708 číslicích
Graficky stránku obohatili Conrad Rider a Ken Silverman (odkaz viz výše).