Megoldották a Rubik-kocka rejtélyét

Akárhogyan keverjük össze a Rubik-kockát, az ki lehet rakni legfeljebb húsz lépésből. Egy nemzetközi kutatócsoport legalábbis erre a megállapításra jutott, a húszas számot pedig elnevezték Isten számának.

De kezdjük az elején. Harminc évvel ezelőtt egy brit kutató találta ki, hogy matematikai bizonyítást ad arra, melyik az a legkisebb szám, mellyel ki lehet rakni a Rubik-kockát. Azóta izgatja a téma a rajongókat, az évek alatt többen is próbálkoztak megoldásokkal.

Morley Davidson, a Kenti Állami Egyetem matematika professzora és csapata bebizonyította, hogy a varázsszám a húszas. Több mint százmillió olyan kezdőállás van, melynél pontosan húsz lépésből lehet kirakni a kockát. Ugyanakkor az is igaz, hogy a legtöbb kezdőállásnál 15-19 mozdulat kell a sikerhez.

Egészen 1995-ig úgy gondolták, hogy 18 lépés is elég. Akkor Michael Reid matematikus talált egy olyan kezdőállást, melynél 20 mozdulatra volt szükség ahhoz, hogy kirakják a kockát. Nagyon sokáig azonban inkább csak hinni lehetett ebben, mert bizonyítani senki nem tudta, hogy valóban elég ennyi mozdulat ahhoz, hogy bármely állásból ki tudjuk rakni a kockát – magyarázta Davidson professzor. Azt is elárulta, hogy mielőtt nekiálltak volna a bizonyításnak, azt remélték, hogy 21 lesz a szám. A legtöbbet Michael Reid foglalkozott a probléma kutatásával, többször is előállt különböző elméletekkel, az utóbbi években pedig a mostani csapatban benne lévő Tomas Rokicki foglalkozott a bűvös szám kutatásával.

A bizonyítás

Az összes lehetséges kezdőállás 43 trillió, a kutatók 2,2 milliárd csoportba osztották a lehetséges kezdőállásokat, mindegyik csoportban 20 milliárd pozíció volt. Már az elején látták, hogy teljesen reménytelen lett volna, az összes végigmodellezése, így ki kellett találni valamit, amivel jelentősen lecsökkentik ezt a számot. Ha például fejjel lefelé fordítjuk a kockát, attól nem lesz nehezebb kirakni, de egy új kombinációt jelent – amit ki lehet szűrni a szimmetria miatt. Ezzel és más hasonló módszerekkel sikerült lecsökkenteni a csoportok számát 56 millióra.

Egy nagyon jó számítógépnek is nagyon sok idejébe került volna kiszámolni az összes kombinációt, így a kutatócsoport szuperszámítógépet keresett. Ekkor lépett képbe a Google, ami számítógépeket bocsátott a kutatók rendelkezésére, így néhány hétig tartott csak a folyamat. Első lépésben a számítógépeknek végig kellett próbálni minél több kombinációt. Az idő előrehaladtával kiderült, hogy a húsznál több lépés valószínűsége nagyon kicsi lett. Ezért következtetett arra Davidson és csapata, hogy legfeljebb húsz lépésből mindegyik kombiniációból ki lehet rakni a Rubik-kockát. A kutatást publikálták is.

A legnehezebb állások

Azt már tizenöt éve tudják, hogy vannak olyan kombinációk, melyeknél kell húsz mozdulat ahhoz, hogy kirakjuk a kockát, de most az állítják, hogy ennél több mozdulat soha nem kell. Ugyanakkor a húsz lépéses kezdőállás elég ritka, nagyjából háromszázmillió ilyen állás van. A legtöbb variáció a 18 mozdulatnál lehetséges, utána következik a 17 mozdulat.