Kategórie:
5
6
7
8
9

Zadanie

Vo svete dračích korytnačiek je náročné prežiť a preto sa matky korytnačky hrávajú s malými korytnačiatkami takúto hru: Na ploche znázornenej na obrázku je päť korytnačiatok. Dve matky korytnačky sa striedajú v ťahoch. Matka korytnačka si môže vybrať jeden z dvoch ťahov:

  • zvolí si korytnačiatko, ktoré má za sebou alebo na svojej úrovni iné korytnačiatko, a posunie ho o ľubovoľný počet políčok dopredu, alebo
  • posunie o 1 políčko dopredu všetky korytnačiatka, ktoré za sebou nemajú iné korytnačiatko.

Ak matka korytnačka presunie korytnačiatko na políčko s príšerou, na konci trasy, príšera korytnačiatko zje. Matka korytnačka, ktorá toto spraví, prehrá. Ktorá matka korytnačka má víťaznú stratégiu? Víťazná stratégia znamená, že jedna matka korytnačka vie voliť také ťahy, aby vyhrala bez ohľadu na to, aké ťahy vykonáva druhá matka korytnačka.

Vzorové riešenie

Opravovali: Imro, ViktorB, mati

Matky môžu používať tieto dva typy ťahov:

  1. typ:
    Korytnačka si zvolí korytnačiatko, ktoré má za sebou alebo na svojej úrovni iné korytnačiatko, a posunie ho o ľubovoľný počet políčok dopredu.

  2. typ:
    Korytnačka posunie o 1 políčko dopredu všetky korytnačiatka, ktoré za sebou nemajú iné korytnačiatko.

Zamyslime sa nad tým, čo vlastne taká víťazná stratégia je. Je to nejaký jednoznačný postup, ktorým ak sa jeden z hráčov bude riadiť, tak určite vyhrá, bez ohľadu na to, čo bude robiť súper.

Všimnime si, že prehrá hráč, ktorý ako prvý niečo spraví - v tomto prípade umiestni korytnačiatko na deviate políčko s príšerou. Môže nám napadnúť, že pokiaľ druhá matka bude nejakým spôsobom opakovať ťahy po prvej, tak asi nemôže prehrať. Pokiaľ by mala posunúť korytnačiatko na deviate políčko, tak by to len zopakovala po prvej , a teda prvá by už prehrala.

Po tom, ako sme dostali tento nápad, poďme sformulovať našu stratégiu: Pokiaľ prvá matka posunie všetky posledné korytnačiatka o jedno políčko, spraví to aj druhá. Ak posunie jedno korytnačiatko 1. typom z políčka A na políčko B, tak druhá matka posunie nejaké iné korytnačiatko z políčka A na políčko B.

Na to, aby sme ukázali, že táto stratégia vždy funguje, musíme ukázať niekoľko vecí:

  1. Dáka korytnačka prehrá

  2. Ak sa druhá matka bude riadiť vyššie popísanou stratégiou tak neprehrá

  3. Druhá matka sa vždy môže riadiť vyššie popísanou stratégiou

Nejaká korytnačka prehrá

Je jasné, že táto hra nemôže byť nekonečne dlhá a nemôže skončiť remízou, takže dáka korytnačka určite prehrá. Toto je dôležité povedať, lebo nikde ďalej nehovoríme, prečo prvá matka stúpi na prehrávajúce políčko, iba to, že druhá tam stúpi až po prvej.

Ak sa druhá matka bude riadiť stratégiou, tak neprehrá

Uvedomme si, že políčko, na ktorom sa nachádza posledné korytnačiatko, sa 2. typom ťahu môže zmeniť iba o 1. Prvým typom sa nezmení, lebo za posunutým korytnačiatkom vždy aspoň jedno ešte ostane.

Toto znamená, že druhá matka druhým typom ťahu určite žiadne korytnačiatko neposunie na deviate políčko. Pokiaľ totiž druhý typ použije vždy iba po tom, čo ho použila prvá matka, tak ním korytnačiatka vždy posunie na nejaké párne políčko, lebo v posúvaní sa striedajú (po každom pohybe prvej matky nasleduje rovnaký pohyb druhej) a začína prvá posunom na políčko nepárne.

Ani keď prvá matka posunie jedno korytnačiatko z políčka A na políčko B, tak druhá matka neprehrá, pretože tiež posunie korytnačiatko na políčko B, čo nemôže byť 9, lebo potom by prvá matka prehrala prvá.

Môže druhá matka ťah prvej vždy opakovať?

Pokiaľ prvá matka posunie všetky posledné korytnačiatka o 1, tak druhá matka to určite vie spraviť tiež, vždy budú dáke posledné korytnačiatka, ktoré môže posunúť.

A ak prvá matka nejaké korytnačiatko posunie z A na B, tak musí platiť, že na A je ešte aspoň jedna korytnačka, ktorá sa dá pohnúť na políčko B, inak by to druhá matka nevedela zopakovať. Teda ak A je posledné políčko s korytnačiatkami, tak tam musia ostávať ešte aspoň 2.

Na začiatku je na poslednom mieste kde sú korytnačiatka nepárny počet (5) a na ostatných párny (0). Pokiaľ druhá matka vždy opakuje po prvej, tak sa to nikdy nezmení. Korytnačky sa zakaždým hýbu buď v dvojiciach, 2 ubudnú z políčka A a pribudnú na políčko B, teda nezmení sa parita počtu korytnačiek, alebo sa dvakrát pohnú všetky posledné korytnačky o jedno políčko. Posledné políčko s korytnačiatkami sa vlastne spojí s dvomi inými políčkami, a teda ostáva na ňom nepárny počet, keďže na oboch tých políčkach je počet párny.

Takže druhá matka vie zopakovať pohyb korytnačiatkom z políčka A na políčko B vždy, pretože pokiaľ je políčko A posledné políčko s korytnačkami, tak na ňom bol predtým nepárny počet vyšší ako jedna, inak by týmto korytnačiatkom prvá matka mohla hýbať iba druhým typom ťahu. Pokiaľ políčko A nebolo posledné, bol na ňom párny počet, iný ako 0 teda teraz je nepárny a je tam teda aspoň jedna korytnačka, ktorou druhá matka môže pohnúť.
Teda vidíme, že druhá matka určite môže vždy opakovať, a určite pri tom neprehrá.

Komentár

Príklad bol vcelku ťažký takže sme radi, že ste sa s ním popasovali, aj keď ste dostali menej bodov, tak dúfame, že sa vám páčil. Čo sa častých chýb týka, tak viacerí z vás zabudli povedať, prečo druhá matka korytnačka vie opakovať ťahy po prvej. Ide o dôležitú časť, lebo bez nej si nemôžeme byť istý, že nenastane situácia pri ktorej by naša stratégia nehovorila čo má druhá matka spraviť.