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

Podúloha A (15 bodov):

Existuje veľa ľahko popísateľných postupov. Náš obľúbený je nasledovný: Na začiatku si čísla rozdelíme do dvojíc – \(1\) s \(2\), \(3\) so \(4\), \(5\) so \(6\), …, až \(49\) s \(50\). Každú dvojicu od seba odčítame, čím na papieri dostaneme \(25\)-krát číslo \(1\). Jednu jednotku si „odložíme nabok”. Ostatných \(24\) rozdelíme do \(12\) dvojíc. Každú dvojicu jednotiek škrtneme a namiesto nej dostaneme nulu. V tejto chvíli teda máme na papieri jednu \(1\) a dvanásť \(0\). A odtiaľto je už cesta do cieľa zjavná, ba priam by sa dalo povedať, že už nie je čo pokaziť :)

Ďalší podobný spôsob je „odložiť si nabok” \(1\) a \(2\) a zvyšok popárovať do dvojíc „obkročmo” – \(3\) s \(5\), \(4\) so \(6\), \(7\) s \(9\), \(8\) s \(10\), …, \(47\) so \(49\) a \(48\) s \(50\). Takto nám vznikne \(24\)-krát číslo \(2\), ktoré keď popárujeme, tak vznikne \(12\)-krát číslo \(0\). Už iba ostáva odčítať \(2 - 1 = 1\) a odčítať všetky \(0\) od \(1\).

Ďalší funguje tiež podobne – „odložiť si nabok” \(1\) a \(2\) a zvyšok popárujeme do dvojíc „viac obkročmo” – \(3\) so \(6\), \(4\) so \(7\), \(5\) s \(8\), \(9\) s \(12\), \(10\) s \(13\), \(11\) so \(14\), …, \(45\) so \(48\), \(46\) so \(49\) a \(47\) s \(50\). Vznikne nám \(24\)-krát číslo \(3\), z ktorých vznikne \(12\)-krát číslo \(0\). Posledný krok je opäť odčítať \(2 - 1 = 1\) a odčítať všetky \(0\) od \(1\).

Podúloha B (25 bodov):

Každé číslo na papieri je nezáporné, minimum je teda \(0\). Najväčšie číslo na začiatku je \(50\). Každé ďalšie číslo vznikne ako rozdiel dvoch už existujúcich. Nikdy preto nevyrobíme číslo väčšie ako \(50 − 0 = 50\). Ostáva už len dodať, že Adam vie napísať aj číslo \(50\). Toto vieme dosiahnuť napr. nasledovne: \(3 − 2 = 1\), \(1 − 1 = 0\), \(50 − 0 = 50\).

Podúloha C (30 bodov):

Kto si vyskúšal všetky možné priebehy škrtania, ktoré začína tým, že sú na papieri napríklad len čísla \(1\), \(2\), \(3\), \(4\), si mohol všimnúť, že posledné číslo na konci je vždy párne. Naopak, ak sú na začiatku na papieri čísla od \(1\) po \(5\), skončíme vždy s nepárnym výsledkom. Stačí sa pozerať na to, koľko máme v ktorej chvíli na papieri nepárnych čísel:

• Rozdiel dvoch párnych čísel je párny. Ak teda preškrtneme dve párne čísla, napíšeme nové párne číslo. Počet nepárnych sa nezmenil.
• Aj rozdiel dvoch nepárnych čísel je párny. Ak teda preškrtneme dve nepárne čísla, napíšeme nové párne číslo. Počet nepárnych klesol o \(2\).
• Rozdiel nepárneho a párneho čísla (v ľubovoľnom poradí) je vždy nepárny. Ak teda preškrtneme nepárne a párne číslo, napíšeme namiesto nich nepárne číslo. Počet nepárnych čísel na papieri sa teda opäť nezmenil.

Čo sa teda stane, ak máme na začiatku na papieri čísla od \(1\) do \(50\)? Nepárnych čísel medzi nimi je presne \(25\). Po niektorých škrtaniach sa ich počet zmenší, ale vždy presne o \(2\). Preto vždy bude na papieri nepárny počet nepárnych čísel –- a teda aspoň jedno. Z toho už je zjavné, že úplne na konci, keď nám už ostalo jedno jediné číslo, musí toto číslo byť nepárne. Nech teda Adam škrtá ako len chce, číslo \(14\) na konci hry dosiahnuť nemôže.

Podúloha D (30 bodov):

Už vieme, že posledné číslo musí byť nepárne a musí ležať medzi \(0\) a \(50\). Zostáva ukázať, že hociktoré takéto číslo vieme vyrobiť. Zovšeobecníme prvý postup z podúlohy A. Povedzme, že chceme na konci vyrobiť číslo \(2k + 1\) (pre nejaké \(k > 0\)). „Odložíme si nabok” čísla \(1\) a \(2k + 2\). Ostatné čísla popárujeme za radom do dvojíc. Všimnime si, že v každej dvojici sa čísla líšia o \(1\). (Príklad: Nech \(k = 3\). Nabok si odložíme čísla \(1\) a \(8\). Páry, ktoré vyrobíme, budú \(2-3\), \(4-5\), \(6-7\), \(9-10\), \(11-12\), . . . , \(49-50\).) Postupne každý pár škrtneme a napíšeme jeho rozdiel, teda číslo \(1\). Máme \(24\) párov, dostaneme teda \(24\) jednotiek. Tieto popárujeme, dostaneme \(12\) núl. No a teraz už len od seba odčítame \(2k + 2\) a \(1\), čím dostaneme želané číslo \(2k + 1\). V tejto chvíli máme na papieri jedenkrát číslo \(2k + 1\) a dvanásťkrát číslo \(0\). Poškrtať čísla do úspešného konca už určite zvládnete.