Patnáctka
Úloha číslo: 2453
Najděte kritérium pro řešitelnost hlavolamu „Patnáctka“.
Jde o hlavolam, kde je v mřížce \(4\times 4\) umístěno 15 čtvercových kamenů očíslovaných od 1 do 15, místo jednoho kamene je však volné místo, které umožňuje kameny posouvat. Na začátku jsou kameny libovolně zamíchány, cílem hry je seřadit je od 1 do 15.
Cílem této úlohy je charakterizovat rozmístění, která lze takto seřadit. Pro začátek se zaměřte na pozici, kde kameny jsou srovnány tak, že čísla 14 a 15 jsou navzájem vyměněná jako na obrázku.
Nápověda
Uvažte následující pořadí políček:
Uspořádání ze zadání je podle tohoto pořadí reprezentováno permutací \((1, 2, 3, 4, 8, 12, 14, 15, 13, 9, 5, 6, 7, 11, 10)\) a pokuste se odvodit nějaký vztah pro čísla kamenů v tomto pořadí.
Řešení
Pozice v patnáctce si budeme pamatovat jako čísla kamenů \(1{,}2,…,15\) uspořádané podle pořadí políček (i jiný souvislý tah po šachovnici by byl možný). Dostaneme nějakou permutaci čísel \(1,…,15\).
Zbývá si uvědomit, že každý tah zachovává znaménko permutace, t.j. řešitelné pozice mají znaménko \(+1\), neřešitelné \(-1\). Vždy totiž posouváme kámen mezi políčky s lichým a se sudým indexem, tzn. že počet kamenů, který jsme v permutaci přeskočili je sudý. Jinými slovy, tahy odpovídají skládáním s lichými cykly a proto se znaménko permutace nemění.
Poznámka na okraj: Samuel Lloyd (1841–1911), zpopularizoval tento hlavolam v roce 1878 tím, že vyhlásil, že prémii $1.000 získá ten, kdo nalezne přípustnou posloupnost tahů, která prohodí políčka 14 a 15. Z řešení příkladu vidíme, že to nelze, ovšem dvě triková „řešení“ jsou na následujících obrázcích.
První trikové řešení - jiné umístění prázdného políčka:
Druhé trikové řešení - otočení mřížky:
