Zoznam úloh

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

Zadanie

Všeobecný slovenský chudobný študent chcel kúpiť svojim malým súrodencom Adamovi a Eve hru. Nemal však veľa peňazí, tak im len vytlačil pravidlá. Na začiatku hry je na papieri napísaná postupnosť čísel $1,\, 2,\, 3,\, 4,\, \dots,\, 19,\, 20$. Hru začína Adam a následne sa strieda s Evou v ťahoch. Hráč vo svojom ťahu umiestni znamienko $+$ alebo $-$ pred niektoré číslo, ktoré ešte nemá znamienko. Keď už všetkých $20$ čísel má znamienko, hra končí. Potom Eva zje toľko medovníkov, aká je absolútna hodnota súčtu čísel na papieri.

Eva chce zjesť čo najviac medovníkov a Adam chce, aby ich Eva zjedla čo najmenej. Nájdite najlepšiu stratégiu pre Adama a najlepšiu stratégiu pre Evu.[^1] Koľko medovníkov spapá Eva, ak ona aj Adam budú hrať podľa svojich najlepších stratégií?


  1. Najlepšia stratégia pre Evu je taká stratégia, ktorou vie Eva zaručiť, že zje aspoň $m$ medovníkov bez ohľadu na to, ako hraje Adam. Navyše, $m$ je najväčšie možné. Obdobne, najlepšia stratégia pre Adama je taká stratégia, ktorou vie Adam zaručiť, že Eva zje nanajvýš $n$ medovníkov bez ohľadu na to, ako ona hraje. Navyše, $n$ je najmenšie možné.

Ú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$.

Pre odovzdávanie sa musíš prihlásiť.
Trojsten

Korešpondenčný matematický seminár zastrešuje občianske združenie Trojsten.

Kontakt
Ďalšie projekty