Kategórie:
5
6
7
8
9

Zadanie

AnkaP a Lychondražej dohadujú cenu: Striedavo dopĺňajú namiesto hviezdičiek v rovniciach celé čísla. Začína AnkaP. \\∗ = ∗ \\∗ + ∗ = ∗ \\∗ + ∗ + ∗ = ∗ \\∗ + ∗ + ∗ + ∗ = ∗ \\∗ + ∗ + ∗ + ∗ + ∗ = ∗ \\∗ + ∗ + ∗ + ∗ + ∗ + ∗ = ∗ \\∗ + ∗ + ∗ + ∗ + ∗ + ∗ + ∗ = ∗ \\ Zistite, či môže AnkaP dosiahnuť, aby po poslednom ťahu boli pravdivé všetky rovnosti bez ohľadu na to, ako bude hrať Lychondražej.

Vzorové riešenie

Opravovali: Peter, alica, mati

Aby sa nám ľahšie vysvetľovalo, zaveďme si nasledovné označenie. Rovnosti, v ktorých je nepárny počet nedoplnených hviezdičiek, budeme volať "nepárne", tie s párnym počtom zas "párne".

Hráč, ktorý dopĺňa do rovnosti číslo za hviezdičku ako posledný, určuje či bude rovnosť platiť. Vie si vypočítať, pre ktoré celé číslo rovnosť platí. Ak práve toto číslo doplní, rovnosť bude platiť. Ak doplní ľubovoľné iné, rovnosť platiť nebude. To znamená, že ak AnkaP vie dosiahnuť aby po poslednom ťahu určite všetky rovnosti platili, musela v každej z nich dopĺňať číslo ako posledná.

Na začiatku máme 4 párne rovnosti a 3 nepárne. Ako prvý krok AnkaP doplní ľubovoľné číslo do nepárnej rovnosti. Teraz máme teda 5 párnych rovností a 2 nepárne. Ďalšie kroky sa budú odvíjať od toho, čo urobí Lychondražej:

  1. Vždy keď doplní číslo do nejakej z párnych rovností, doplní do tej istej rovnosti číslo aj AnkaP.
    Po tomto jej ťahu bude táto rovnosť zase párna, keďže sa počet hviezdičiek zníži o 2.
  2. Keď Lychondražej doplní číslo do niektorej z nepárnych rovností, AnkaP doplní hviezdičku do druhej nepárnej rovnosti. Vtedy už budú všetky rovnosti párne.

V tejto časti chceme ukázať, že sa AnkaP vie držať vyššie popísanej stratégie a ak sa jej držať bude, tak zaručene vyhrá, nech by sa Lychondražej aj na hlavu postavil.

  1. Ak Lychondražej doplní hviezdičku v rovnosti s párnym počtom hviezdičiek, tak AnkaP vie doplniť hviezdičku v tej istej rovnosti. Pred Lychondražejovým ťahom boli v danej rovnosti aspoň 2 hviezdičky (najmenší nenulový párny počet), po ňom aspoň jedna a teda podľa kroku 1) to AnkaP spraví.
  2. Lychondražej nemôže stále dopĺňať hviezdičky v párnych riadkoch. Počet hviezdičiek v párnych riadkoch je konečný (20). My ich striedavo vypĺňame, čím sa ich počet nakoniec po poslednom ťahu AnkyP zníži na 0. Takže najneskôr vtedy Lychondražej bude musieť doplniť hviezdičku do nepárneho riadku.
  3. Po Lychondražejovom ťahu do nepárneho riadku dá AnkaP číslo do posledného nepárneho riadka, do ktorého ešte nebol spravený ťah a týmto spraví všetky riadky párnymi.
  4. Predstavme si posledný Lychondražejov ťah v ľubovoľnom párnom riadku. Vďaka bodu a. vieme, že aj po tomto ťahu v párnom riadku vie doň AnkaP doplniť číslo. No a keďže to bol Lychondražejov posledný ťah v tomto riadku, tak AnkaP dopĺňa poslednú hviezdičku, čím zaručí platnosť rovnice.

V bode a. sme ukázali, že AnkaP vie v párnych riadkoch doplniť hviezdičku po každom Lychondražejovom ťahu. V bodoch b. a c. sme ukázali, že sa AnkeP podarí zo všetkých nepárnych riadkov spraviť párne. A nakoniec v bode d. sme ukázali, že AnkaP vie doplniť každý párny riadok tak, aby platil. Z toho vyplýva, že vie doplniť správne každý riadok.

Iné riešenie

Existuje aj ďalšia výherná stratégia pre AnkuP. Tá spočíva v tom, že AnkaP sa bude vyhýbať dopĺňaniu predposledných hviezdičiek v rovnostiach lebo by Lychondražej mohol doplniť poslednú hviezdičku tak, že rovnosti platiť nebudú. Naopak, bude sa snažiť do dopĺňania predposledných hviezdičiek donútiť Lychondražeja. Jej ťahy budú vyzerať takto:

  1. Dopĺňa ľubovoľne do rovností, kde sú aspoň tri hviezdičky.
  2. Akonáhle Lychondražej doplní v nejakej z rovností predposlednú hviezdičku, ona doplní tú poslednú a rovnosť tak bude platiť. Keďže to urobí hneď, nikdy sa nemôže stať, že pred ťahom AnkyP budú dve alebo viac rovností s jednou hviezdičkou. To je dôležité lebo inak by mohla doplniť iba jednu rovnosť a ďalšiu by mohol na svojom ťahu Lychondražej doplniť nesprávne.

Môže AnkaP vždy urobiť jeden z krokov? Nemohla by jedine vtedy, keby v každej z rovností boli pred jej ťahom práve dve alebo žiadne hviezdičky. To znamená, že celkovo by nevyplnených hviezdičiek musel byť párny počet. Celkový počet hviezdičiek je 35, teda nepárny. AnkaP ide prvá a strieda sa s Lychondražejom. Z toho jasne vidíme, že pred jej ťahom vždy zostáva nepárny počet hviezdičiek. To znamená že sa AnkaP bude môcť vždy držať svojej stratégie, Lychondražej bude musieť doplniť vždy predposlednú hviezdičku, ona poslednú a tak vie dosiahnuť že budú všetky rovnosti platiť.

Komentár

Ahojte, väčšina z vás prišla na jednu z týchto dvoch výherných stratégií. Môžeme si všimnúť, že pri oboch stratégiách sa niekde spomínalo, či je nejaký počet (hviezdičiek, ťahov) párny alebo nepárny. To je pri úlohách kde hľadáme spôsob ako určite vyhrať, hlavne keď sa striedajú dvaja hráči, veľmi často využiteľné. Z toho nám priamo vychádza aj prvá stratégia, akýmsi spôsobom opakovať ťahy druhého hráča.