Zadanie

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.

Podúloha a)

Vieme, že Miško vyhrá. Ako teda bude vyzerať posledný ťah? Janko zoberie posledné prskavky z krabice. Spraví to však iba v prípade, že nebude mať na výber, čiže vtedy, ak v krabici zostane už len jedna prskavka. Ťah pred ním mohol mať Miško v krabici \(2\), \(3\), \(4\) alebo dokonca aj \(5\) prskaviek. Z tohoto počtu totiž vždy dokázal zobrať toľko, aby Jankovi zostala posledná prskavka. Janko vedel, že ak Miškovi v krabici zostanú \(2\), \(3\), \(4\) alebo \(5\) prskaviek, prehrá. Takže ak by mohol, snažil by sa týmto štyrom situáciam vyhnúť. Lenže on sa im nevyhol. To znamená, že keď sa dostal na ťah, musel mať v krabici práve \(6\) prskaviek. Pri takom počte prskaviek totiž nemá na výber. Nech spraví ľubovoľný ťah, Miško sa ocitne v situácii, z ktorej vie vyhrať.

Presnejšie, môžu nastať tieto štyri prípady:

  • Janko zoberie \(1\) prskavku. Potom Miško zoberie \(4\), Jankovi zostane posledná a prehrá.
  • Janko zoberie \(2\) prskavky. Potom Miško zoberie \(3\), Jankovi zostane posledná a prehrá.
  • Janko zoberie \(3\) prskavky. Potom Miško zoberie \(2\), Jankovi zostane posledná a prehrá.
  • Janko zoberie \(4\) prskavky. Potom Miško zoberie \(1\), Jankovi zostane posledná a prehrá.

Môžeme si všimnúť, čo majú tieto ťahy spoločné. V každom prípade zoberú chlapci dokopy \(5\) prskaviek. A to je základom Miškovej stratégie. Nech Janko urobí čokoľvek, Miško vie jeho ťah doplniť tak, aby spolu zobrali \(5\) prskaviek. Ak by napríklad pred Jankovým ťahom bolo v krabici \(16\) prskaviek, po ťahu oboch chlapcov by tam Miško nechal \(11\), potom \(6\) a nakoniec \(1\). Nech by Janko spravil akýkoľvek ťah, Miško by svoj cieľ vždy dosiahol. A v krabici by Jankovi zostala posledná prskavka.

Teraz už určite vieme, akým spôsobom Miško vyhrá. V prvom ťahu musí zobrať jednu prskavku a nechať Jankovi v krabici \(41\) prskaviek. A potom zakaždým doplniť Jankov ťah tak, aby dokopy zobrali práve \(5\) prskaviek. Takto bude počet prskaviek v krabici na začiatku Jankovho ťahu postupne \(41\), \(36\), \(31\), \(26\), \(21\), \(16\), \(11\), \(6\) a nakoniec \(1\).

Uvedomme si, že to, čo sme zistili, platí aj všeobecne. Nech si zoberieme krabicu s ľubovoľným počtom prskaviek, vieme zistiť, ktorý hráč vyhrá, ak bude môcť brať iba \(1\), \(2\), \(3\) alebo \(4\) prskavky. Môžeme si všimnúť, že Miško sa snažil dostať Janka do situácie, v ktorej počet prskaviek dával po delení číslom \(5\) zvyšok \(1\). Miško sa preto bude vo svojom úplne prvom ťahu snažiť znížiť počet prskaviek v krabici tak, aby táto vlastnosť platila. Potom totiž môže dopĺňať Jankov ťah na \(5\) prskaviek a vyhrať. Jediný prípad, kedy sa mu to nepodarí spraviť je, ak je v krabici na začiatku \(5k+1\) prskaviek pre ľubovoľné \(k\). V tom prípade je vo výhode Janko, lebo môže použiť Miškovu stratégiu proti Miškovi a dopĺňať každý Miškov ťah tak, aby dokopy zobrali \(5\) prskaviek. Takýmto postupom bude Miško ten, komu zostane posledná prskavka a Janko vyhrá.

Podúloha b)

V predchádzajúcej časti sme postupovali od konca a zisťovali, ktorý z chlapcov vyhrá. V tejto časti nás k podobnému postupu zadanie dokonca navádza (chlapci otvárali krabice postupne). Poďme sa teda na to pozrieť lepšie.

Nebudeme však zisťovať, či vyhrá Miško alebo Janko, ale či hráč, ktorý je na ťahu vyhrá alebo prehrá. Inými slovami, keď si zoberieme krabicu, chceme zistiť, či pre hráča, ktorý spraví prvý ťah, existuje víťazná stratégia alebo prehrá bez ohľadu na to čo spraví.

  • Ak máme jednu prskavku, hráč na ťahu ju musí zobrať a prehrať.
  • Ak máme dve prskavky, hráč na ťahu zoberie jednu a druhú nechá protihráčovi, ktorý prehrá.
  • Pri troch prskavkách vie prvý hráč buď zobrať všetky alebo zobrať jednu, nechať protihráčovi druhú a sám potom zobrať tretiu. V oboch prípadoch prehrá.
  • Pri štyroch prskavkách môže hráč na ťahu zobrať jednu a nechá súpera v situácii troch prskaviek, v ktorej, ako sme už zistili, protihráč nemá šancu. Začínajúci hráč teda vyhrá.
  • Pri piatich prskavkách môže hráč na ťahu zobrať štyri a nechať súperovi jednu.
  • Pri šiestich prskavkách vieme zobrať tri a znova nechať prehrávajúce tri súperovi.
  • Podobne to je aj pri siedmich prskavkách, ak zoberieme štyri.
  • Pri ôsmich prskavkách môžeme zobrať päť a znova nechať súperovi tri.
  • Pri deviatich prskavkách však nemáme šancu. Nech zoberieme ľubovoľný povolený počet z nich, dostaneme súpera do situácie, z ktorej sa mu (podľa toho, čo sme už zistili), podarí vyhrať.

Čo vieme zistiť z týchto úvah? Vidíme, že pri nejakom počte prskaviek v krabici (\(1\), \(3\) a \(9\)) hráč, ktorý je na ťahu nemá šancu vyhrať, nech spraví čokoľvek. A pri zvyšných krabiciach existuje pre začínajúceho hráča ťah, ktorý mu zaručí výhru.

Uvedomme si ale jednu dôležitú vec. Ak sme začali napríklad s krabicou, ktorá obsahovala \(19\) prskaviek, potom obaja hráči odobrali nejaké prskavky a Miško je zrazu v situácii, že je na ťahu a v krabici zostáva \(9\) prskaviek. V tomto prípade teda určite prehrá. Je jedno, čo sa stalo predtým a aké ťahy chlapci robili. Jediné, na čom záleží je, koľko prskaviek je v krabici v tomto momente.

Ak teda chceme vyrátať, kto vyhrá, ak bude v krabici \(10\) prskaviek, vieme to zistiť pomocou predchádzajúcich menších riešení (ktoré máme hore spísané). Postupne sa pozrieme, aké ťahy vieme spraviť, ak začíname s \(10\) prskavkami. Ak nás aspoň jeden ťah vedie do situácie, kde je zaručené, že hráč na ťahu prehrá, chceme ho spraviť. Lebo na ťahu bude náš súper a teda prehrá. Ak však všetky ťahy vedú do situácií, kde hráč na ťahu vyhrá, znamená to, že prehráme my bez ohľadu na to, čo spravíme.

Všetky situácie môžeme označiť ako vyhrávajúce (\(V\)) a prehrávajúce (\(P\)). Pomocou týchto dvoch pravidiel a znalosti všetkých situácií s menším počtom prskaviek sme schopní vyplniť nasledujúcu tabuľku:

Počet prskaviek 1 2 3 4 5 6 7 8 9 10
Prvý hráč P V P V V V V V P V
Počet prskaviek 11 12 13 14 15 16 17 18 19 20
Prvý hráč P V V V V V P V P V

Keďže prvý hráč je vždy Miško, vieme pre každý počet prskaviek povedať, kto vyhrá.

Opäť sa tento postup dá uplatniť všeobecne a pri rôznych hrách môžeme zaviesť prehrávajúce a vyhrávajúce pozície (samozrejme, od konkrétnej hry závisí, ako presne budú vyzerať). Obe pravidlá však zostávajú platné tak, ako sú:

  • Pozícia je vyhrávajúca, ak existuje ťah, ktorý nás dostane do prehrávajúcej pozície.
  • Pozícia je prehrávajúca, ak všetky ťahy vedú do vyhrávajúcich pozícií.

Podúloha c)

2015 prskaviek je trochu veľa, skúsme sa však pozrieť aspoň na niektoré menšie počty prskaviek v krabici za rovnakých podmienok ťahania. Podobne ako v predchádzajúcej časti, aj tu si vieme vytvoriť tabuľku:

Počet prskaviek 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Prvý hráč P V P V V V V P V P V V V V

Môžeme si všimnúť, že tabuľka začína vzorom PVPVVVV, ktorý sa po 7 prskavkách opakuje, pričom vzor vždy končí násobkom sedmičky. Keďže platí \(2016 = 7 \cdot 288\), tabulka pre veľké počty prskaviek bude vyzerať takto:

Počet prskaviek 2010 2011 2012 2013 2014 2015 2016
Prvý hráč P V P V V V V

Víťazom bude opäť Miško.

Tento postup si však vyžaduje predpoklad, že vzor PVPVVVV sa opakuje naprieč všetkými možnými veľkosťami krabíc. Môžeme si však uvedomiť, že keď zisťujeme výsledok pre nejaký počet prskaviek, pozeráme sa len na počty o jedno, tri alebo štyri menšie. To znamená, že výsledok závisí od najviac štyroch predchádzajúcich výsledkov. Ak sa teda zopakujú prvé štyri výsledky PVPV, tak sa náš vzor začne opakovať automaticky. A tieto prvé štyri výsledky sa naozaj zopakujú pri počtoch \(8\)\(11\).

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.