3. Koľko Medovníkov Spapáš? (κ ≤ 3) vzorové riešenie

Úlohy, kde hľadáme optimálnu stratégiu pre dvoch je potrebné zvyčajne riešiť tak, že výsledok dokážeme ohraničiť zhora aj zdola. V našom prípade to znamená ukázať, že Eva vie za akýchkoľvek podmienok zjesť aspoň \(n\) medovníkov a tiež to, že Adam dokáže za akýchkoľvek podmienok hrať tak, aby ich viac nebolo. Je tiež dôležité si uvedomiť, že ak je nejaká stratégia najlepšou v každom momente hry, nemusí to znamenať, že je najlepšia aj pre celú hru.

V prvej časti ukážeme, že Eva zje vždy aspoň \(30\) medovníkov. Prečo? Vezmime si čísla od \(1\) do \(20\) a rozdeľme ich do dvojíc tak, že \(1\) a \(2\) sú spolu, \(3\) a \(4\) atď. Keďže Adam začína, musí vybrať nejaké číslo a dať mu znamienko. Eva následne vyberie číslo, s ktorým je Adamovo číslo vo dvojici a priradí mu opačné znamienko. Jedinou výnimkou je dvojica \(19, 20\), v tejto dá Eva rovnaké znamienko obom číslam. Čo tým dosiahne? \(19\) a \(20\) jej dajú v absolútnej hodnote \(39\), vo zvyšných deviatich dvojiciach nám určite vznikne v súčte číslo medzi \(-9\) a \(9\). Adam samozrejme môže prideliť \(19\)-ke alebo \(20\)-ke opačné znamienko ako má súčet zvyšných \(9\) dvojíc, z čoho vyplýva, že hodnota zmení znamienko. Eva teda zje určite aspoň \(39-9=30\) medovníkov.

Teraz nám ešte treba ukázať, že Adam má stratégiu, ktorá nedovolí Eve zjesť viac ako \(30\) medovníkov. Adam najprv priradí číslu \(20\) znamienko \(+\) a rozdelí si čísla od \(2\) po \(19\) do dvojíc. Veľmi podobnými spôsobom, ako je hore uvedené, v nich vie dosiahnuť \(+1\) alebo \(-1\) (zapíšeme to ako \(\pm 1\)). Avšak len dokým Eva nepoužije číslo \(1\). Ak sa to stane skôr ako na konci, vyberie najväčšie nepoužité číslo a tomu dá znamienko \(-\). Následne bude čakať, či mu Eva túto jeho dvojicu doplní. Ak nedoplní, doplní on dvojicu, ktorú týmto ťahom Eva načala a v nej tak do súčtu dostane \(\pm1\). Eva môže jeho dvojicu doplniť opačným znamienkom, čo jej ale nepomôže (\(\pm1\)), alebo rovnakým. Ak Eva jeho dvojicu doplní, musí Adam otvárať ďalšiu dvojicu. Vyberie si najvyššie nepoužité číslo a použije znamienko opačné k tomu, aké použil naposledy, keď otváral novú dvojicu. Súčet v novej dvojici je vždy v absolútnej hodnote menší ako v predošlej dvojici s rovnakými znamienkami, z čoho vyplýva, že súčet všetkých čísel v dvojiciach s rovnakými znamienkami bude stále medzi \(-37\) a \(0\). Pozrime sa teraz, aký bude pri Adamovej stratégii celkový súčet:

• za dvojicu \(1\), \(20\) máme do súčtu buď \(19\) alebo \(21\), podľa toho, či je pri \(1\)-ke \(+\) alebo \(-\);
• za dvojice s rôznymi znamienkami číslo medzi \(-9\) a \(9\);
• za dvojice s rovnakými znamienkami dostaneme vždy záporné číslo medzi \(-37\) a \(0\).

Z toho vyplýva, že hodnota súčtu bude vždy medzi \(21+9+0=30\) a \(20-1-9-37=-27\), teda absolútna hodnota bude menšia alebo rovná ako \(30\). Čo bolo treba dokázať.

Z vyššie uvedených poznatkov vyplýva, že v prípade, že obaja hrajú najlepšie ako vedia, Eva zje \(30\) medovníkov.

Druhá časť inak: Adamova stratégia bude tentoraz iná: Vyberie vždy najvyššie nepoužité číslo a dá mu znamienko opačné, ako má doterajší súčet, ak je súčet \(0\), bude to \(+\). Prečo takáto taktika funguje? Podľa taktiky Adam začne \(+20\)-kou. Rozdeľme si ťahy na jednotlivé kolá. Nech \(i\)-te kolo je to, v ktorom sa naposledy zmení znamienko(alebo je nulové) celkového súčtu. V prvých \(i-1\) ťahoch sme už určite využili čísla \(20, \cdots , 20-(i-2)\). V \(i\)-tom páre môžeme teda pridať do absolútnej hodnoty \(20-(i-1) + 20-i = 41-i\). Vieme tiež, že predtým bol súčet opačného znamienka alebo nulový, teda po i-tom ťahu bude súčet maximálne \(41-i\). Vo zvyšných \(10-i\) kolách však hodnota bude už len klesať(Adam vždy vezme najvyššie číslo a to je opačného znamienka ako Evino číslo) a to aspoň o jedna. Na konci teda súčet bude nanajvýš \((41-i)-10=31-i \leq 30\).