Počet bodov:
Popis:  15b

Ak máte akékoľvek otázky ohľadom tejto úlohy napíšte Majke Vajdovej na

Janko s Miškom a Peťkou sa rozhodli stráviť posledného Silvestra na chate v horách. Aby sa nenudili, Peťka im nakúpila prskavky (Janko ani Miško veľmi petardy nemusia). Keď konečne nadišiel večer, chlapci zistili, že to s tými prskavkami nebude také jednoduché. Prskavky sú všetky zabalené vo veľkých a škaredých krabiciach. Takže, keď prskavky domíňajú a dopraskajú, krabicu treba vyhodiť (Peťka je veľmi poriadkumilovná a povaľujúce sa krabice by nezniesla). A najbližší smetný kôš je dobrý kusisko cesty vo fujavici, hlbokom snehu a ľade.

Takže Miško si (v tej istej sekunde ako Janko) uvedomil, že on určite nechce byť ten, kto zoberie poslednú prskavku z krabice a bude sa musieť brodiť v snehu. Zároveň ale ani jeden z nich nechcel zobrať z krabice príliš veľa prskaviek naraz, aby nevyzeral chamtivo. A tak si obidvaja vybudovali dobrú stratégiu, ako brať prskavky z krabice. Ale vždy musí niekto zobrať tú poslednú…

Úloha

Táto úloha sa bude skladať z niekoľkých podúloh. V každej časti bude krabica s istým počtom prskaviek. Je určené, koľko prskaviek môže jeden človek z krabice zobrať. Janko s Miškom budú striedavo brať z krabice prskavky, pričom vždy začína Miško. Vašou úlohou je povedať, kto prehrá a bude musieť zobrať poslednú prskavku a ísť vyhodiť krabicu.

Navyše, obaja chlapci sú veľmi múdri a preto robia najlepšie možné ťahy. Ak hráč môže spraviť nejaký ťah, ktorý ho povedie k výhre bez ohľadu na to ako bude hrať druhý hráč, tak ho spraví.

Napríklad, ak môžu naraz zobrať z krabice \(1\), \(2\) alebo \(3\) prskavky a v krabici už zostávajú len \(4\) prskavky, Miško, ktorý je práve na ťahu, určite zoberie \(3\) prskavky. V takom prípade bude musieť Janko zobrať poslednú prskavku a vyniesť krabicu. Keby namiesto toho zobral Miško len jednu alebo dve prskavky, Janko by zobral toľko prskaviek, aby v ďalšom ťahu zostala v krabici len jedna prskavka a Miško by prehral.

  1. (4 body) V krabici máme \(42\) prskaviek. Chlapci môžu zakaždým zobrať \(1\), \(2\), \(3\) alebo \(4\) prskavky. Dokonca vám prezradíme, že v takejto situácii je zaručené, že Miško (ktorý začína) vie vyhrať. Musí však robiť správne ťahy. Vašou úlohou je popísať stratégiu, ktorú má dodržiavať, aby vyhral bez ohľadu na to, čo spraví Janko. Stratégiou myslíme to, že poviete v akej situácii má potiahnuť aký počet prskaviek. Pri popise vašej stratégie nezabudnite zdôvodniť, prečo je správna a prečo Janko, nech ťahá akokoľvek, vždy prehrá.

    Príkladom stratégie by bolo napríklad: Ak Janko zobral \(3\) prskavky zober \(1\) prskavku, inak zober \(2\) prskavky. Je na vás si rozmyslieť, že táto stratégia nie je dobrá, lebo sa Janko vie správať tak, aby vyhral.

  2. (6 bodov) Neskôr si chlapci zobrali \(20\) krabíc, ktoré postupne otvárali. Prvá krabica obsahovala jednu prskavku, druhá dve, tretia tri až dvadsiata obsahovala dvadsať prskaviek. Zakaždým mohli z krabice zobrať \(1\), \(3\), \(4\) alebo \(5\) prskaviek (zobrať \(2\) prskavky nebolo povolené). Pre každú z týchto krabíc zistite, pre ktorého hráča existuje zaručená stratégia, pomocou ktorej vyhrá. Napríklad pri prvej krabici určite vyhrá Janko.

    Vaše riešenie by malo naviac obsahovať popis toho, ako ste zisťovali, ktorý z hráčov vyhrá.

  3. (5 bodov) Nakoniec im už zostala len jedna obrovská krabica, ktorá mala v sebe \(2015\) prskaviek. Rozhodli sa, že v jednom ťahu z nej môžu zobrať len \(1\), \(3\) alebo \(4\) prskavky. Zistite, ktorý z hráčov vyhrá a popíšte postup, ako ste sa k tomuto riešeniu dostali.

Odovzdávanie

Na odovzdávanie sa musíš prihlásiť

Otázky a diskusia

Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.