Úloha 1.u4: Uvězněni (5 b)

Zadáno v čísle 22.1.

Řešeno v čísle 22.3.

Zadání

Strážce zajal oba cestovatele a rozhodl se jim zadat úkol. Pustí je pouze v případě, že se jim podaří úkol splnit.

Nejdříve strážce pozve prvního cestovatele do místnosti, kde před ním na klasické šachovnici (8×8 polí) rozloží mince tak, aby na každém políčku byla právě jedna. Některé umístí nahoru rubem a některé lícem (jinak jsou mince zcela totožné). Poté strážce cestovateli prozradí jedno pole, říkejme mu únikové. Následně musí první cestovatel otočit jednu libovolnou minci. Pak strážce prvního cestovatele odvede a pozve druhého. Jeho úkolem je na základě rozložení mincí na šachovnici poznat, které pole je únikové. Pokud uspěje, jsou oba cestovatelé volní.

Před plněním úkolu si mohou cestovatelé domluvit strategii. Strážce ale jejich rozhovor odposlechne a zvolí rozložení mincí i únikového pole tak, aby pokud možno neuspěli.

Existuje pro cestovatele strategie, aby je strážce vždy pustil? Pokud ano, jaká?

Řešení

Když přijde druhý cestovatel do místnosti, má k dispozici pouze rozložení mincí na šachovnici. Je tedy jasné, že každé rozložení mincí na šachovnici by mělo ukazovat na jedno konkrétní pole.

I při příchodu prvního cestovatele do místnosti rozložení mincí na šachovnici kóduje nějaké konkrétní pole. Cestovatel musí být schopen otočením právě jedné mince docílit toho, aby rozložení šachovnice ukazovalo na jakékoli zadané pole.
Šachovnice má 64 polí a cestovatel musí otočit jednu z 64 mincí - otočení každé z mincí tedy musí vést na jiné pole.

Otázkou zůstává, jak vymyslet šikovné kódování polí šachovnice pomocí rozložení mincí. Očíslujme si pole šachovnice (libovolně) 0 až 63. Jako dobrý nápad by se mohlo zdát například sčítat hodnoty všech polí, kde je mince lícem nahoru, a
tento součet modulo 64 označit za číslo výsledného pole. To skoro funguje, občas ale první cestovatel může narazit na problém, že by potřeboval přičíst minci číslo $k$, která už ale je lícem nahoru, nebo odečíst minci $(64-k)$, která je ale nahoru rubem.

Tento nedostatek můžeme vyřešit tak, že místo klasického sčítání použijeme operaci XOR (tedy sčítání čísel převedených do dvojkové soustavy bez přenosu). Tato operace má všechny vlastnosti sčítání, které potřebujeme $^1$, a navíc vždy platí $a\ \mathrm{XOR}\ a = 0$, takže přičtení i odečtení čísla vede ke stejnému výsledku.

Shrňme si možné řešení úlohy: Pole šachovnice očíslujeme od 0 do 63. První cestovatel přijde do místnosti a spočítá XOR hodnot všech polí, na kterých mince leží lícem nahoru. Označme tuto hodnotu $P$. Pokud únikové pole je $U$, otočí minci na poli $P\ \mathrm{XOR}\ U$. Druhý cestovatel po příchodu opět spočítá XOR hodnot všech polí, kde je mince lícem nahoru. Vyjde mu $P\ \mathrm{XOR}\ (P\ \mathrm{XOR}\ U) = U$, zná tedy únikové pole.

Využití operace XOR bylo možno též obejít pomocí různých tabulek nebo postupných součtů vždy jen vybraných sloupců či řádků. Nepřišla nám ani dvě správná řešení, která by se alespoň trochu nelišila.

Kuba


$1$ Poznámka pro algebraiky: XOR je klasické sčítání definované na vektorovém prostoru nad
dvouprvkovým tělesem.