8. Kustódi Maraudéra Stíhajú vzorové riešenie

Vzorové riešenie sme sa rozhodli napísať iteratívnym spôsobom. Začneme zjednodušenou verziou úlohy a vytvoríme k nej triviálne riešenie. Postupne si budeme úlohu sťažovať a následne naše riešenie upravíme, aby riešilo aj novú úlohu. Rozhodli sme sa vzorové riešenie napísať práve týmto spôsobom, aby bolo pre čitateľa čo najzrozumiteľnejšie. Je dobré si však uvedomiť, že pri takomto štýle spisovania riešenia konáme istú nadprácu.

Triviálne zjednodušenie

Zadanie. Predstavme si najväčšie možné zjednodušenie úlohy tak, aby sa nám zachovala jej pointa. Nech vnútro Citadely je priamka¹ a nech sa väznica nachádza na fixnom bode \(0\)². Zlodej si teda môže vybrať smer, ktorým bude z väznice utekať a vzdialenosť, o ktorú sa každý deň posunie.

Riešenie. Naším cieľom je zaručiť, že nám zlodej nebude vedieť unikať donekonečna. Inak povedané: „Pri našom algoritme vykonávania domových prehliadok si zlodej nevie vybrať taký smer a vzdialenosť úniku za jeden deň, že po akomkoľvek počte dní bude stále na slobode.“ Domové prehliadky sa rozhodneme vykonávať nasledovným algoritmom. Prvú noc sa pozrieme na súradnicu \(0\) na priamke. Druhú noc si vypočítame, kam by sa už zlodej dostal, keby sa rozhodol ísť dennou rýchlosťou \(1\) a v tom dome spravíme prehliadku – čiže v dome so súradnicami \(2\). Tretiu noc si zase vypočítame, kam by sa zlodej stihol za 3 dni dostať, keby šiel dennou rýchlosťou \(-1\) a spravíme tam prehliadku. Ďalšiu, štvrtú, noc si zase spočítame, v akom dome by sa zlodej nachádzal, keby šiel dennou rýchlosťou \(2\)... Tento postup domových prehliadok by sme mohli zovšeobecniť, ale my sa rozhodneme tak nespraviť. Jednak by to bolo zbytočne komplikované a vlastne to ani nepotrebujeme. Ako sme si už povedali, na splnenie zadania nám stačí pre každú dennú rýchlosť, ktorú nám dokáže zlodej podstrčiť ukázať, že: „Aha, tu máš nejaký konkrétny deň a od tohto dňa už budeš určite trčať v base, lebo sme ťa nejakú noc predtým chytili pri domovej prehliadke.“ Povedzme, že sa teda zlodej vybral po priamke nejakou všeobecnou dennou rýchlosťou \(v\)³. Lenže my použitím vyššie spomínaného algoritmu za \(2\cdot|v|+1\) nocí spravíme niekoľko domových prehliadok. Tieto prehliadky robíme tak, že sa postupne stretne práve raz so zlodejom, ktorý by sa rozhodol ísť rýchlosťou \(0, 1, -1, 2, \dots, v, -v\). Teda sa stretneme aj so zlodejom, ktorý ide dennou rýchlosťou \(v\). Potom od dňa \(2\cdot|v| + 2\) bude zlodej v base, a teda sme vyhrali.

1. iterácia triviálnej úlohy

Zadanie. Zmeňme teraz úlohu tak, že vnútro Citadely je síce už rovina, ale zlodej si vie zvoliť za čísla pohybu \(a\), \(b\) iba hodnoty z množiny nezáporných celých čísel. Predpokladajme tiež, že väznica sa nachádza na fixnom bode \((0, 0)\).

Riešenie. Budeme musieť nájsť taký algoritmus, že ním postupne prejdeme všetky možné hodnoty \((a, b)\). Skúsme takýto. Najprv vykonáme prehliadky v domoch na súradniciach \((a, b)\) takých, že \(a + b = 0\). Až s týmto skončíme, tak potom vykonáme prehliadky v domoch na súradniciach \((a, b)\), takých, že \(a + b = 1\) a takto postupujeme ďalej. Teda ak skončíme s vykonaním všetkých domových prehliadok na súradniciach \((a, b), a + b = n\), tak začneme vykonávať prehliadky domov na súradniciach \((a, b), a + b = n+1\). Samozrejme nenavštevujeme priamo domy na súradniciach \((a, b)\), ale vždy si dopočítavame, že kde by sa práve nachádzal zlodej v daný deň, keby si vybral hodnoty pohybu \((a, b)\). Ostáva nám ešte ukázať, že nech si zlodej vyberie akúkoľvek všeobecnú dvojicu \((a, b)\), tak vieme povedať, že po konečnom počte dní už bude určite v base. Zrejme keď skončíme s prehliadkami všetkých možností \((x, y), x + y = a + b\), tak sa nejakú noc stretneme aj v dome so zlodejom, ktorý si zvolil dvojicu \((a, b)\).⁴. A teda od nasledujúceho dňa už bude zlodej v base, čím sme vyhrali. Poznamenajme ešte, že kým bude zlodej zaručene chytený, tak urobíme prehliadky v domoch \((x, y), x + y \leq a + b\). Urobením hrubého horného odhadu prídeme na to, že takýchto usporiadaných dvojíc nemôže byť viac ako \((a + b + 1)^2\), čo je počet všetkých usporiadaných dvojíc, kde aj \(x \leq a + b\) aj \(y \leq a + b\). Teda po takomto počte dní bude zlodej už určite chytený a tento počet je konečný.

2. iterácia triviálnej úlohy

Zadanie. Zmeňme teraz úlohu tak, že vnútro Citadely je rovina a zlodej si vie zvoliť za \(a, b\) akékoľvek celé čísla. Predpokladajme stále, že väznica sa nachádza na fixnom bode \((0, 0)\).

Riešenie. Na vyriešenie tohto problému nám stačí upraviť predošlý algoritmus tak, že najprv prejdeme postupne všetky možnosti \((a, b), |a| + |b| = n\) také, že \(a, b\) sú najprv obe nezáporné, potom \(a\) je záporné a \(b\) je nezáporné, potom \(a\) je nezáporné a \(b\) je záporné a na záver \(a, b\) sú obe záporné. Potom na dolapenie zlodeja, ktorý si zvolil dvojicu \((a, b)\) potrebujeme vykonať len 4-krát viacej domových prehliadok ako v predošlom prípade, čo je stále konečne veľa.

Posledná iterácia (Skutočná úloha)

Zadanie. Zoberme si už konečne pôvodné zadanie úlohy. Vnútro Citadely je rovina, zlodej si za \(a, b\) volí akékoľvek celé čísla a väznica sa môže nachádzať hocikde v priestore.

Riešenie. V skutočnosti táto úloha sa oproti predošlej o moc nelíši. Jediný rozdiel je, že nevieme, kde sa nachádza väznica. Máme však už postup, ako robiť domové prehliadky, aby sme zlodeja na rovine chytili vždy, keď má väznica fixnú pozíciu. Upraviť tento algoritmus tak, aby sme vedeli chytiť zlodeja vždy, aj keď nevieme, kde sa nachádza väznica už vôbec nie je ťažké. Stačí nám si namiesto usporiadanej dvojice \((a, b)\) položiť usporiadanú štvoricu \((a, b, x_0, y_0)\) kde \(x_0, y_0\) sú neznáme pozície väznice. Potom upravíme náš algoritmus nasledovne. Necháme policajtov najprv vykonať⁵ všetky domové prehliadky typu \((a, b, x_0, y_0)\) také, že \(|a| + |b| + |x_0| + |y_0| = 0\). Potom ak policajti skončia všetky prehliadky typu \(|a| + |b| + |x_0| + |y_0| = n\), tak prejdú na prehliadky typu \(|a| + |b| + |x_0| + |y_0| = n\). Zrejme pomocou takéhoto postupu sa eventuálne policajti stretnú s akýmkoľvek zlodejom, nech by ten zlodej vyrazil z hocijakej väznice a vybral si akýkoľvek typ pohybu. Ostáva už len overiť, že policajti takto chytia akéhokoľvek zlodeja v počte dní. Využitím myšlienky z predminulej iterácie vieme, že počet usporiadaných štvoríc \((a, b, x_0, y_0)\) takých, že \(|a| + |b| + |x_0| + |y_0| \leq n\) je menší, nanajvýš rovný počtu usporiadaných štvoríc \((a, b, x_0, y_0), |a| \leq n, |b| \leq n, x_0 \leq n, y_0 \leq n\). Tiež vieme, že všetky usporiadané štvorice obsiahnuté v prvej možnosti sú obsiahnuté aj v druhej možnosti a počet usporiadaných štvoríc v druhej možnosti vieme ľahko vypočítať. Analogickou úvahou z predminulej iterácie teda dospejeme k tomu, že počet usporiadaných štvoríc \((a, b, x_0, y_0)\) takých, že \(|a| + |b| + |x_0| + |y_0| \leq n\) nie je väčší, ako \(4n^4\)⁶. No a \(4n^4\) je konečné číslo, preto nech by si zlodej zvolil akékoľvek celé čísla \(a, b, x_0, y_0\), tak vieme zaručiť, že po \(4(|a| + |b| + |x_0| + |y_0|)^4\) dňoch už bude zlodej určite zatknutý.

Posledné slová na záver. Dodajme ešte, že táto úloha je v istom zmysle podobná rozhodovacej úlohe, či majú racionálne čísla rovnakú mohutnosť ako prirodzené čísla – teda, či ich je tiež spočítateľne veľa. Ak ste dostali až sem a neviete o tom, skúste si to sami dokázať prípadne zalovte v hlbinách Internetu. Ukrývajú sa tam zaujímavé poznatky o mohutnosti množín.