Lloydova patnáctka a permutace

Úkol: Lloydova10patnáctka je hra s $ 4\times 4$ hracími poli s ploškami (figurami) očíslovanými 1 až 15, přičemž číslo 16 je vyjmuto, viz (13). Úkolem je přesouvat hrací figury a docílit standardního pořadí, kdy po řádkách zleva vpravo čteme čísla 1 až 15. Pozice patnáctky tedy odpovídá permutaci $ i\mapsto p(i)$, kde $ i=1,2,\dots, 16$ a $ p(i)$ je číslo na pozici, kde má být správně $ i$.

a)
Zjistěte, jak se chová znak příslušné permutace při vykonání tahu a jak se mění pozice prázdného pole 16, a vytvořte veličinu, která se zachovává při každém tahu. Dokažte takto, že nelze složit patnáctku, pokud jsou jen dvě figury (např. 14 a 15) prohozené. Obecněji dokážete, že nelze složit konfiguraci s prázdným polem vpravo dole, ovšem figurami 1 až 15 permutovanými lichou permutací.

b)
Nalezněte vhodné základní tahy, které generují cyklickou permutaci polí. Užijte výsledku k důkazu, že libovolnou sudou permutaci s prázdným polem vpravo dole naopak složit lze. Máte velkou volnost, jak k problému přistoupit, naše řešení je jednou z mnoha možností.


Řešení:


a) V jazyce permutací $ i\mapsto p(i)$ pro $ i=1,\dots, 16$ není tah nic jiného než transpozice nějakého čísla s číslem 16 (prázdným polem). Každá transpozice je lichou permutací, proč tedy tvrdíme, že lze získat jen sudé permutace? Důvod je v tom, že každý tah zároveň mění o jednu buď číslo řádky s prázdným polem $ r$, nebo číslo sloupce s prázdným polem $ s$, kde $ r,s=1,2,3,4$. Díky tomu veličina

$\displaystyle Z=\mathop{\rm znak}\nolimits p \cdot (-1)^{(r+s)}$ (12)

se zachovává, protože tah mění obě znaménka. Pokud tedy uvažujeme dvě konfigurace s dírou vpravo dole, $ r=s=4$, které mají opačný $ \mathop{\rm znak}\nolimits p$, nelze je zjevně spojit libovolnou posloupností tahů, jelikož mají opačné $ Z$.


b) Dokažme nyní, že se lze sekvencí tahů dostat z libovolné sudé permutace s dírou na místě $ r=s=4$ do standardní pozice 1 až 15 po řádkách. Jelikož prázdné pole $ 16$ je v počátečním i koncovém stavu na místě, uvažujme nyní jen permutace 15 prvků. Pro větší názornost následujících úvah přelepme kameny $ 1,2,3,4,\dots$ nálepkami $ 10',9', 6',5',\dots$ podle obrázku

\begin{displaymath}\begin{array}{\vert c\vert c\vert c\vert c\vert} \hline 1&2&3...
...e 12'&15'&1'&3'\\ \hline 13'&14'&2'&\times\\ \hline \end{array}\end{displaymath} (13)

V pravé tabulce (13) vidíme, že kameny $ 1',2',3',\dots 15'$ vytvářejí cyklus ve tvaru zdvojeného písmene {\bb H} (viz obrázek 6 vlevo); tato tabulka také ukazuje cílové srovnání čárkovaných kamenů. Je tedy jasné, že lze těchto 15 kamenů cyklicky permutovat (a díru ponechat na místě); příslušnou permutaci značme $ H$. Kromě toho máme cyklickou permutaci 3 kamenů $ 1',2',3'$, kterou označíme $ C$ (obrázek 6 vpravo). Všimněte si, že obě permutace obsahují lichý počet kamenů, a jsou tedy sudé.

Obrázek: Užitečné permutace kamenů v Lloydově patnáctce.
\includegraphics[scale=0.5]{OBRAZKY/patnactka.eps} =1mm(-75,12)$ H:$(-33,12)$ C:$

Ačkoliv užití pouze dvou cyklů $ C,H$ je neekonomické pro praktické použití, je velmi efektivní pro teoretické účely. Při vhodné orientaci $ H$ (jako na obrázku 6) je jasné, že permutace $ C_k= H^k C H^{-k}$ se chová jako $ C\equiv
C_0$, ovšem cyklicky permutuje kameny $ (k+1)', (k+2)', (k+3)'$ modulo 15. Permutace $ C_k$ nám ve skutečnosti stačí na složení patnáctky11, jelikož libovolný kámen na začátku lze ,,probublat'' na správné místo. Začněme třeba s kamenem $ 15'$ a pokračujme sestupně. Problém může nastat až v poslední fázi, kdy se snažíme přemístit kameny $ 1',2',3'$, zatímco kameny $ 4'$ a výše už jsou na správných místech. Povede se nám to jen v případě, že jsme začali se sudou permutací. Čtenář jistě detaily domyslí sám.

$ \ast$LM$ \ast$