Student World

***pravidelné páteční „přetištění“ staršího článku. Změnilo se od té doby něco?

Časy slávy Rubikovy kostky jsou v době (už stejně odeznívající) mánie kolem sudoku sice pryč, ale matematické hádanky zůstávají. Jaký je maximální počet tahů, jimž lze kostku složit z libovolné pozice?

Na Northeastern University došli profesor Gene Cooperman a jeho student Dan Kunkle k závěru, že se jedná o 26 tahů. Dosavadní důkaz byl o tah delší. Již před deseti lety profesor kalifornské univerzity UCLA Richard Korf přišel s tvrzením, že průměrný počet kroků (respektive median) ke složení kostky je 18 a že podle něj žádná pozice nebude odolávat více než 20 tahů, toto tvrzení se mu ale nepodařilo dokázat.

Zdroj:
http://www.neu.edu/nupr/news/0407/rubik.html

Mimochodem, v tiskové zprávě Northeastern University je jako rok vynálezu Rubikovy kostky uvedeno 1970, podle Wikipedie k tomu došlo v roce 1974 (http://en.wikipedia.org/wiki/Rubik%27s_Cube). Ať tak či onak, jak vidno, nějaký čas tedy trvalo, než se kolem kostky rozpoutala mánie.

Zajímavé je, že podle Wiki není většina dosavadních důkazů týkajících se kostky konstruktivních, tj. neuvádějí řešení, jak kostku složit. Podle tiskové zprávy Northeastern University nový důkaz ale naopak konstruktivní je: program, které napsali, skutečně prošel všechny pozice kostky a ukázal, jak je lze složit v 26 tazích. Řešení bylo dosaženo hrubou silou díky výkonnému hardwaru (7TB distribuovaný disk jako rozšíření RAM) a optimalizovaným algoritmům. Všechny pozice byly rozděleny do určitých skupin konfigurací, na které pak šlo aplikovat stejný postup a zjistit jeho výsledek pro všechny konfigurace. Optimalizace spočívala hlavně v předpočítávání, kdy se nejprve příslušná konfigurace poměrně dlouho analyzovala, aby se zjistilo, do jaké skupiny patří. Vlastní složení pak už bylo velmi rychlé.
Matematický aparát, ze kterého se při této úloze vychází, je teorie grup.

Diskuse na Physorg.com (včetně otázky, kdy problém půjde spočítat prostě hrubou silou bez jakékoliv optimalizace)
http://forum.physorg.com/index.php?showtopic=15328

Vlastní článek Kunkleho a Coopermana
http://www.ccs.neu.edu/home/gene/papers/rubik.pdf

Poznámka: Jistá paralela s tím, jak byl dokázán problém čtyř barev?

autor Pavel Houser