Sbírka matematických úloh

Lloydova patnáctka

Úloha číslo: 2453

• Nápověda

  Uvažte následující pořadí políček, tedy uspořádání vlevo je 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ů utříděná 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), vynalezl tento hlavolam v roce 1878 a vyhlásil, že prémii \(\$1000\) 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 jedno půvabné trikové řešené skýtá stránka
  http://www.holotronix.com/samlloyd15c.html.