2. Komprimácia Možných Súčtov (κ ≤ 2) vzorové riešenie

Keď riešime úlohu ako táto, je na úvod dôležité zamyslieť sa, akým spôsobom sa mení počet párnych a nepárnych čísel. Môže nám to napadnúť pomerne jednoducho – ak hrá parita rolu v tom, ako čísla mažeme, bude isto dôležitá aj pre číslo, ktoré nám napokon zostane.

Pozrime sa, ako sa zmení počet nepárnych čísel po niektorom z ťahov, pričom zatiaľ zanedbáme ich hodnotu. Zadanie nám hovorí, že ak máme dve nepárne čísla, nahradíme ich nulou. To znamená, že sme prišli o dve nepárne čísla. Ak si vezmeme jedno nepárne a jedno párne číslo, počet nepárnych čísel sa nezmení. Podobne sa nezmení ani v prípade, keď vezmeme dve párne čísla.

Zistili sme, že počet nepárnych čísel sa nám po každom ťahu buď zníži o dve alebo zostane rovnaký. To je veľmi dôležité, pretože ak je na začiatku počet nepárnych čísel nepárny, tak taký aj zostane, a teda ako posledné nám zvýši nepárne číslo. Podobne, ak je tento počet párny, zostávajúce číslo musí byť párne. Pozrime sa na to, pre aké \(n\) bude počet nepárnych čísel nepárny.

Ak si rozdelíme prirodzené čísla na štvorice tak, ako idú po poradí, zistíme, že v každej z nich sú práve dve nepárne čísla. Prvé z nich je v štvorici prvé, druhé z nich je tretie. Teda ak skončíme s písaním čísel na tabuľu v momente, keď má \(n\) zvyšok po delení štyrmi rovný \(1\) (má tvar \(n=4k+1\), kde \(k\) je celé číslo) alebo \(2\), napíšeme na tabuľu nepárny počet nepárnych čísel. V opačnom prípade bude ich počet párny.

Pozrime sa teraz na to, aké najmenšie číslo nám na tabuli môže zostať v prípade, ak je počet nepárnych čísel párny. Vieme už, že tam zostane párne číslo. Číslo, ktoré na tabuli zostane, nemôže byť záporné, skúsme teda ukázať, že najmenšie číslo, ktoré vieme dostať bude \(0\). Dôležité je, že potrebujeme ukázať, že to pôjde vždy, nestačí nám konkrétny príklad. Získať nulu na konci je možné napríklad takto: Vieme, že z dvojice párne – nepárne, nám vždy zostane nepárne číslo. Takto sa môžeme zbaviť všetkých párnych čísel a zostane nám len párny počet nepárnych čísel. Tie môžeme dať do dvojíc a získať tak len nuly. Napokon sčítaním dvoch núl dostaneme vždy len nulu, a teda sa ostatných núl zbavíme a zvýši nám jedna.

Ak je počet nepárnych čísel na tabuli nepárny, naisto nám na konci zvýši nepárne číslo. Najmenšie, ktoré sa na tabuli môže objaviť je \(1\). Vieme čísla mazať tak, aby tam napokon zvýšila práve jednotka? Vieme. Podobne ako predtým sa najprv zbavíme párnych čísel a zostanú nám len nepárne. Tých je ale nepárny počet, takže môžeme všetky čísla okrem jednotky dať do dvojíc a spraviť z nich nuly. Takto dostávame niekoľko núl a jednu jednotku. Na konci nám takto vždy môže zostať len číslo \(1\).

Aké môžeme v takejto situácii(ak je počet nepárnych čísel nepárny) získať naopak čo najväčšie číslo? Vieme už, že na tabuli na konci zostane nepárne číslo. Na základe ťahov, ktoré máme k dispozícii môžeme vidieť, že väčšie nepárne číslo ako niektoré z pôvodných na tabuľu dostať nevieme. Dokážeme na tabuli udržať najväčšie z nepárnych čísel? Áno. Veľmi podobne, ako sme sa dopracovali k číslu \(1\) sa vieme aj k iným ostatným nepárnym číslam. Jednoducho ich nezaradíme do žiadnej z dvojíc nepárnych čísel. V závislosti od toho, či \(n\) bolo párne alebo nepárne tak dostávame buď číslo \(n-1\) alebo \(n\).

Záverečnou časťou úlohy je nájsť najvyššie možné zostávajúce číslo, ak bol na tabuli na začiatku párny počet nepárnych čísel. Vieme, že číslo, ktoré nám zostane, bude párne. Z toho, aké môžeme robiť ťahy môžeme vidieť, že súčet párnych čísel na tabuli sa nám nemôže zväčšiť a zároveň, že nepárne čísla nám k zvyšovaniu najväčšieho čísla na tabuli nepomôžu. Najväčšie číslo, aké by sme teda mohli na tabuľu dostať je súčet všetkých párnych čísel. Stačí nám už len ukázať, že ho na tabuľu dostať vieme a tiež, že ho tam vieme udržať až do konca.

Súčet všetkých párnych čísel získame jednoducho: sčítame ich. Takto nám zostane párny počet nepárnych čísel a jedno veľké párne. Ako sme sa už naučili doteraz, z párneho počtu nepárnych čísel vieme spraviť nulu, keď ich dáme do dvojíc. A keďže nula je párne číslo, súčtu párnych čísel neublíži.

Ešte je otázka, aký bude súčet všetkých párnych čísel: Rozdeľme si situáciu podľa zvyškov po delení štyrmi, teda buď \(n=4k\) alebo \(n=4l+3\). V prvom prípade sčítavame čísla \(2, 4, \cdots 4k\). Môžeme vidieť, že ich je párny počet, nakoľko v každej štvorici sú dve a štvoríc je \(k\). Súčet všetkých párnych čísel dostaneme napríklad tak, že si utvoríme dvojičky \((2,4k), (4,4k-2), \cdots\). Týchto dvojičiek je \(k\) a súčet v každej z nich je \(4k+2\), celkový súčet je teda rovný \(k(4k+2) = \frac{1}{4}(n+2)n\). V prípade \(n=4l+3\) môžeme postupovať podobne, pribudlo nám totiž len číslo \(4l+2 = n-1\). Okrem toho netreba zabudnúť, že \(n=4l+3\), teda aj zlomok bude iný. Celkovo je teda súčet rovný \((4l+2)l + (4l+2) = (4l+2)(l+1) = \frac{1}{4}(n-1)(n+1)\).