Patnáctka

Patnáctku vymyslel kolem roku 1874 americký poštovní úředník Noyes Palmer Chapman¹⁾. Na hrací ploše 4×4 lze přemístit 15 dílků s čísly od 1 do 15. Cílem hry je dosáhnout uspořádné podoby z dané výchozí (neuspořádané) podoby.

Podle vzorce pro permutace je možných 16!   =   1 · 2 · 3 · … · 14 · 15 · 16   =   20 922 789 888 000 kombinací, jak umístit 15 kamenů a jedno prázdné pole na hrací plochu. V polovině těchto případů je však vzniklý soubor úloh neřešitelný. Počet možných podob je tedy „jen“ 10 461 394 944 000.

Ke zjištění, zda je pro danou podobu možné řešení, se používá tzv. parametr přeuspořádání N₁ a řádkový parametr N₂.

• Pro parametr přeuspořádání uvažujte všechny dvojice čísel (m,n), kde m < n, tj. dvojice (1,2), (1,3), …, (1,15), (2,3), (2,4), …, (2,15), (3,4), …, (14,15). Požadované pořadí je znázorněno šipkami. Spočítáme-li nyní ty dvojice čísel, v nichž je druhé číslo ve směru šipek první, získáme parametr přeuspořádání N₁.
• Řádkový parametr N₂ je číslo vodorovného řádku, ve kterém se nachází prázdné pole.

Úloha je pro danou počáteční podobu řešitelná právě tehdy, když je součet N₁ + N₂ sudé číslo.

Příklad:

V zobrazené podobě má následujících 9 dvojic čísel „špatné“ pořadí: (10,11), (10,12), (10,13), (10,14), (11,12), (11,13), (11,14), (12,14), (13,14). Parametr přeuspořádání N₁ má tedy hodnotu 9. Prázdné pole je ve 3. řádku, takže N₂ = 3. Protože součet N₁ + N₂ = 9 + 3 = 12 je číslo sudé, je úloha pro tuto výchozí podobu řešitelná.

Zdroj: Wikipedia (deutsch), článek "15-Puzzle"

Pozn:

¹⁾ Často (a mylně) bývá považován za autora tohoto hlavolamu matematik Sam Loyd. Loyd totiž od roku 1891 až do své smrti tvrdil, že hlavolam vynalezl. Z tohoto důvodu je tato matematická úloha též známa jako tzv. Loydova patnáctka.