5. Král sa zase nudí vzorové riešenie

Podúloha A

Pred každým číslom je buď plus alebo mínus – to sú vždy dve možnosti. Pri každom z \(20\) čísel si znamienko vyberáme nezávisle, dokopy teda bude možností \(2 \cdot 2 \cdot \dots \cdot 2 = 2^{20} = 1\,048\,576\).

Podúloha B

Predstavme si, že Adam nemá napísané všetky čísla hneď na začiatku, ale najprv nemá žiadne, takže výraz má súčet \(0\) (nič tam nie je). Teraz bude postupne pripisovať nejaké čísla a rovno si k nim bude aj vyberať znamienka. Budeme sledovať, ako sa pri tom môže meniť súčet, a čísla skúsime vybrať tak, aby súčet vyšiel pre každú kombináciu znamienok iný.

Začnime napríklad s číslom \(1\): súčet teraz musí byť \(1\) alebo \(-1\). Ďalšiu jednotku zjavne nechceme, skúsme teda pridať napríklad číslo \(2\). Tým dostaneme možné súčty \(-3, -1, 1, 3\). Tu už máme síce viac možností, ale môžeme si všimnúť, že je to stále niečo medzi \(-3\) a \(3\).

Čo dáme ďalšie? Keby sme dali ako ďalšiu \(3\), tak si to pokazíme, lebo potom môžeme súčet \(0\) dostať ako \(1 + 2 - 3\) aj \(-1 - 2 - 3\). Keď dáme ako ďalšie číslo \(4\), potom to už funguje, môžeme si rozpísať všetky možnosti a overiť si to. Dá sa to však aj jednoduchšie. Vieme, že doteraz musel byť výsledok medzi \(-3\) a \(3\). Ak dáme ako ďalšiu \(-4\), tak nový výsledok bude od \(-3 - 4 = -7\) do \(3 - 4 = 1\), a ak si vyberieme \(+4\), tak nový výsledok bude od \(-3 + 4 = 1\) do \(3 + 4 = 7\). Dva výsledky z tej istej skupiny musia byť stále rôzne – to platilo aj pre tie, čo sme mali doteraz, a iba sme ku všetkým pripočítali to isté, takže sa nič nemohlo pokaziť. Dva výsledky z rôznych skupín musia byť takisto rôzne, lebo sú každý z iného rozsahu, ktoré sa neprekrývajú. Máme teda tri čísla, pre ktoré to funguje.

Takto môžeme pokračovať ďalej: ak máme čísla \(1, 2, \dots, 2^n\), o ktorých vieme, že dávajú pre každú kombináciu znamienok iný výsledok, potom k nim môžeme pridať \(2^{n + 1}\) a stále to bude fungovať. Z týchto čísel totiž vieme vyskladať najmenej \(-1 - 2 - \dots - 2^n = -2^{n + 1} + 1\) a najviac \(1 + 2 + \dots + 2^n = 2^{n + 1} - 1\).¹ Ak ku všetkému pripočítame \(-2^{n + 1}\) alebo \(2^{n + 1}\), dostaneme dve skupiny výsledkov, ktoré nemôžu mať žiaden výsledok spoločný, tak ako sme to vysvetlili v predošlom odseku. Stále teda budú všetky výsledky rôzne.

Adam si teda môže vybrať napríklad čísla \(1, 2, 4, \dots, 2^{20}\). Samozrejme, je aj veľa iných možností. Z nášho postupu vidíme, že stačí, aby keď čísla zoradíme od najmenšieho, bolo každé číslo aspoň dvakrát také veľké ako to predchádzajúce.

Ak ste sa s tým ešte nestretli, tak tento postup, ktorý sme práve použili, sa volá matematická indukcia. Ide o to, že dokážeme, že niečo platí pre nejaký malý prípad (ako tu len s jednotkou) a potom dokážeme, že to bude stále platiť, aj keď nejak zmením zadanie (ako tu, že pridáme \(2^{n + 1}\)), čím dostaneme, že to platí pre nejakú väčšiu skupinu prípadov (ako tu všetky postupnosti čísel \(1, 2, \dots, 2^n\)). Je to veľmi užitočné, lebo niekedy sa to ľahšie rieši po takýchto malých krokoch ako celé naraz (ako keby sme mali vymyslieť hneď celú sadu a vyskúšať všetky kombinácie, či funguje).

Podúloha C

Ak ste si skúsili napísať nejakú kombináciu znamienok a potom v nej zmeniť nejaké znamienko (povedzme pri čísle \(n\)), tak rozdiel sa zmení (zväčší alebo zmenší, podľa toho, čo meníme na čo) o \(2n\) – akoby sme ho najprv zmenili na nulu a potom ešte raz na to opačné. Môžeme tu teda použiť podobnú úvahu ako v úlohe z prvého kola: keď meníme znamienka, vždy sa výsledok zmení o niečo párne. Preto keď je raz párny (ako \(42\)), tak z neho určite nedostaneme nepárny (ako \(47\)). Teda sa to nedá.

Podúloha D

V podúlohe B sme ukázali, že sa dá vybrať aj taká kombinácia čísel, že všetky výsledky budú rôzne. Čo sa teraz zmenilo? Stále máme rovnako veľa možností, ako vyplniť znamienka, ale možných výsledkov je už oveľa menej – všetky sú totiž iba od \(-2\,000\) do \(2\,000\) (keď sú tam samé stovky, vieme mať najmenšiu/najväčšiu krajnú hodnotu, ak dáme všade rovnaké znamienka). Dávalo by teda zmysel, že sa tým pádom budú nejaké výsledky dať dosiahnuť viacerými spôsobmi, ale ako to dokážeme?

Ukážme si to najprv na jednoduchšom príklade: máme \(10\) holubov a nejako ich rozdelíme do \(4\) holubníkov. Potom určite budeme mať taký holubník, kde budú aspoň \(3\) holuby. Ak by to tak nebolo, museli by byť všade najviac dvaja, ale potom by ich spolu bolo najviac \(4\cdot 2 = 8\), čo je menej ako \(10\). Rozmyslite si, že všeobecne ak je \(n\) holubov a \(k\) holubníkov, tak existuje holubník, kde je aspoň \(n/k\) holubov. Toto číslo dokonca môžeme zaokrúhliť hore: počet holubov je samozrejme celé číslo a keď vieme, že ich musí byť napríklad aspoň \(2.5\), tak môžeme rovno povedať, že musia byť aspoň \(3\). Tento jednoduchý princíp vie byť v matematike niekedy veľmi užitočný a preto má aj meno, Dirichletov princíp.

Ako ho využijeme tu? Môžeme si predstaviť, že kombinácie znamienok sú holuby a výsledky sú holubníky, každý holub teda bude v jednom holubníku. Holubov je, ako už vieme z podúlohy A, \(2^{20}\). Koľko je holubníkov? Keďže rozsah je od \(-2\,000\) do \(2\,000\), tak ich môže byť najviac \(4\,001\). Z toho dostaneme, že existuje holubník, kde bude aspoň \(263\) holubov.

Zadanie sa však pýta aj na to, či ich musí byť dokonca \(447\), toto nám teda úplne nestačí. V skutočnosti však holubníkov nemôže byť až toľko. Napríklad preto, lebo všetky výsledky musia mať rovnakú paritu, ako sme už zistili v podúlohe C. Takže ich môže byť najviac \(2001\), z čoho dostaneme, že musí byť holubník s dokonca \(525\) holubmi. To už zodpovedá všetky otázky zo zadania, takže tým máme úlohu vyriešenú.