Kategórie:
5
6
7
8
9

Zadanie

AnkaP hrá proti Trhu nasledovnú hru s cenovkami:
Začína AnkaP a potom sa s Trhom strieda v ťahoch. Na začiatku je 10 nepoužitých kartičiek s ciframi od 0 po 9, každá práve jedna. Hráč, ktorý je na ťahu vezme ľubovoľnú nepoužitú kartičku a uloží ju za ostatné použité kartičky doprava. Musí platiť, že po n-tom ťahu, je n-ciferné číslo tvorené použitými kartičkami deliteľné n. Prehrá hráč, ktorý už nemôže spraviť žiaden ťah. Kto má víťaznú stratégiu? Víťazná stratégia znamená, že hráč vie voliť také ťahy, aby vyhral bez ohľadu na to, aké ťahy vykonáva jeho súper.

Vzorové riešenie

Opravovali: matejUuu, stepi

Ešte skôr než budeme hľadať víťaznú stratégiu pre niekoho z hráčov, pozrime sa, ako sa situácia týchto dvoch hráčov líši. Môžeme si všimnúť, že Trh má vždy tie ťahy, kde má jeho číslo párnu dĺžku, takže musí byť deliteľné párnym číslom, a teda musí byť párne. Párne číslo sa musí končiť na párnu číslicu (0, 2, 4, 6, 8), takže Trh môže používať len tieto kartičky. Ak bude tieto kartičky používať aj Anka, tak sa môže stať, že sa všetky minú. Potom by Trh nemal možnosť, ako ďalej hrať, a prehral by.

Skúsme teda podľa toho vymyslieť Anke stratégiu. Bude sa snažiť minúť čo najviac párnych kartičiek, aby ich Trhu ostalo čo najmenej. Keď sa trochu pohráme s možnosťami, môžeme prísť napríklad na takýto začiatok hry:

  • Anka začne 4-kou.
  • Trh môže vyrobiť jedno z čísel 40, 42, 46, 48.
  • Podľa toho Anka urobí jedno z 408, 426, 462, 480.

V niektorých prípadoch (408 a 480) Trh už teraz nemôže pokračovať ďalej, takže Anka by už vyhrala. Ak ale pokračovať môže, tak dá nejakú párnu kartu. Ďalej ide Anka, ktorá určite môže použiť 5-ku, lebo zatiaľ neboli použité žiadne nepárne karty, a keď číslo končí na číslicu 5, tak je určite deliteľné piatimi. Ďalej ide Trh, a musí zahrať poslednú párnu kartu, ktorá je k dispozícii.

To ale znamená, že Trh už určite prehral. V čísle, ktoré takto vznikne, je totiž každá párna cifra a ešte 5-ka, takže ciferný súčet tohto čísla je 0+2+4+5+6+8=25. To nie je deliteľné tromi, takže ani to číslo nemôže byť deliteľné tromi, a teda ani šiestimi. Trh teda nemôže zahrať žiadnu kartu.

Ak bude Anka postupovať podľa tejto stratégie, tak Trh určite prehrá, buď v štvrtom alebo šiestom kole.

Iné riešenia

Toto nie je zďaleka jediné riešenie tejto úlohy. Anka má v skutočnosti veľa rôznych víťazných stratégií. Na to, aby sme niektorú z nich našli, nemusíme prísť na všetky veci, ktoré sa spomínali vo vzorovom riešení. Namiesto toho nám stačí pozrieť sa na všetky možnosti, ako sa hra môže odohrať, a vybrať pre Anku také ťahy, aby vždy vyhrala (tak, ako sme to robili pri prvých troch kolách).

Poznámka: Keď takto skúšame všetky možnosti, tak pri ťahoch Trhu musíme rátať s každým ťahom, ktorý môže urobiť, aby Anka vedela vyhrať bez ohľadu na to, čo urobí Trh. Na druhej strane, pri Ankiných ťahoch si stačí vybrať jednu z jej možností, keďže je to jej stratégia. Teda napríklad ak niekedy môže dať aj 0, aj 2, a v oboch prípadoch vie hru vyhrať, stačí, ak dá vždy povedzme 0, a dvojku nemusíme vôbec spomínať. Stratégia stále funguje a riešenie je stručnejšie a prehľadnejšie. Viacerí ste tam ale písali všetky tieto možnosti, čo nebolo treba.

Komentár

Väčšina vašich riešení využívala nejakú kombináciu týchto dvoch prístupov. Väčšinou ste si uvedomili, že Anke sa oplatí minúť párne čísla, a potom ste vyskúšali všetky možné ťahy Trhu osobitne, až do konca. Zopár riešení dokonca nevyužilo ani to, a Anka začínala napríklad 1-tkou, no napriek tomu vždy dokázala vyhrať.