Úloha 6.u2: Honba za liškou (3 b)

Zadáno v čísle 22.6.

Řešeno v čísle 22.8.

Zadání

Obrázek 1: Počáteční rozestavení lišek a myslivců.

V lese o velikosti 40 polí stojí 2 myslivci (trojúhelníky) a před nimi prchají 2 lišky (kolečka), viz Obrázek 1. Lišky jsou velmi rychlé a chytré. Aby byl hon úspěšný, myslivci je musí chytit. Každý z myslivců se tedy v každém tahu posune o právě jedno pole vodorovně či svisle, v pohybu po úhlopříčce jim brání pravidelně vysazený les. V tu chvíli přestává být pozice lišek bezpečná, proto se každá z nich posune o právě jedno pole podle stejných pravidel jako myslivci. Nyní hon pokračuje opět pohybem myslivců a dál se pohyb lišek a myslivců pravidelně střídá. Liška je ulovena myslivcem, pokud se myslivec přesune na pole, na kterém právě stojí liška. Přesune-li se liška na pole, na kterém právě stojí myslivec, je též ulovena. Ulovená liška vypadává ze hry. Lišky mohou být uloveny postupně.

Poženou se myslivci za liškami donekonečna? Nebo lišky nakonec podlehnou myslivcům, ať se budou snažit sebevíc? Zjistěte, zda existuje pro lišky neprohrávající nebo pro myslivce vyhrávající strategie a popište ji.

Řešení

Lišky budeme chytat postupně. Vybereme si libovolně jednu z nich a dokud ji nechytíme, budeme druhou lišku zcela ignorovat. Myslivce nejdřív přesuneme do úvodní lovecké pozice (viz Obrázek a).

Všimněme si, že pokud se liška nachází v pozici, ze které může ustoupit pouze vpravo, pak je pro ni tato pozice prohrávající. Myslivci se totiž v odpověď posunou též doprava a protože hrací deska je omezená, dojde nejdéle po šesti krocích k tomu, že liška nemůže ustoupit tak, aby nebyla chycena.

a: Úvodní lovecká pozice
b: Krajní případy
Obrázek 2: Lov na lišku

Pokud se liška po rozestavení do úvodní lovecké pozice nachází ve stejném sloupci jako jeden z myslivců, pak se buď nachází vedle některého z nich (v tom případě ji ulovíme), nebo na jednom z míst znázorněných na Obrázku b. Pokud se nachází v horní pozici z Obrázku b, přesuneme oba myslivce nahoru a tím zvítězíme – liška již nemůže udělat tah jinam, než na pole myslivců nebo pole, s nimiž myslivci sousedí. Pokud se nachází ve spodní pozici z Obrázku b, přesuneme oba myslivce dolů, čímž lišku dostaneme do pozice, z níž může prchat pouze doprava – tím jsme zvítězili.

Nyní budeme předpokládat, že liška se nenachází ve stejném sloupci jako nějaký z myslivců. Pokud se liška po svém tahu nenachází ani v sousedním sloupci, přesuneme oba myslivce směrem doprava. Ve chvíli, kdy se liška po svém tahu ocitne v sousedním sloupci nebo ve sloupci myslivce, který je více vpravo, rozlišíme následující možnosti:

Liška se nachází na sousedním poli vedle jednoho z myslivců. Pak ji dalším tahem ulovíme. Liška se nachází v pozici A na Obrázku a. Pak pohneme oběma myslivci směrem nahoru. Liška se nachází v pozici D na Obrázku a. Pak pohneme oběma myslivci směrem dolů. Ve všech ostatních případech pohneme myslivci směrem vpravo.

a: Možné pozice vůči myslivcům
b: Pozice D po pohybu myslivců
Obrázek 3: Lov na lišku

Pokud se liška nacházela v pozici A, pak po přesunu myslivců může utíkat vpravo nebo dolů. Přesune-li se dolů, dostává se vůči myslivcům do pozice B. Pokud se liška nacházela v pozici B, pak po přesunu myslivců může utíkat pouze vpravo – tato pozice je tedy pro lišku prohrávající. Pokud se liška nacházela v pozici C, pak po přesunu myslivců může utíkat vpravo (čímž se dostane opět do pozice C) nebo dolů (čímž se dostane do pozice D). Pokud se liška nacházela v pozici D, pak po přesunu myslivců může utíkat pouze vpravo – tato pozice je tedy pro lišku prohrávající (viz Obrázek b).

Poté co první lišku ulovíme, postavíme opět myslivce do úvodní lovecké pozice a lov zopakujeme pro druhou lišku.

Honza