9. Koľko Miestenka Stojí? vzorové riešenie

Po prvých skúšaniach rôznych postupností ľahko nájdeme pre párne \(n\) postupnosť \(-1,\, +1,\, -1,\, +1,\dots,\, -1,\, +1\). Táto postupnosť zjavne spĺňa nerovnosti zo zadania a \(C_n=2\). Pre nepárne \(n\) ale už nenájdeme takú postupnosť, aj keď sa postupnosť \(1,\, 1/2,\, 1/4,\, \dots,\, 1/2^{(n-2)},\, -2\) veľmi blíži.

Ako prvé pozorovanie si uvedomme, prečo v žiadnej postupnosti nemôžu byť dve nekladné čísla za sebou. Ak by to tak bolo, nazveme si tieto čísla \(x_i\), \(x_{i+1}\) . Potom číslo \(x_{i-1}\) musí byť ale tiež nekladné, pretože musí byť menšie buď ako \(x_{i}\) alebo ako \(x_{i} + C_nx_{i+1}\), no obe tieto čísla sú nekladné. Rovnakým postupom ale aj \(x_{i-2}\) bude nekladné, atď… Preto budú všetky nekladné, čo ale byť nemôžu.

Môžeme si preto úlohu „rozkúskovať“ podľa nekladných čísel. Medzi dvoma nekladnými číslami bude buď jedno, alebo aspoň dve kladné čísla. Tieto skupiny kladných čísel medzi dvoma nekladnými nazvime cyklus. Označme si \(A\) súčet všetkých samotných kladných čísel, t.j. takých \(x_i\), že obe čísla \(x_{i-1}, x_{i+1}\) budú nekladné. Podobne, pre väčší cyklus, kde \(x_i\) a \(x_{j}\) sú nekladné, si označme \(B\) súčet všetkých \(x_{i+1}\) a písmenom \(C\) označme súčet všetkých \(x_{j-1}\). Písmenom \(D\) označme súčet súčtov \(x_{i+2}+x_{i+3}+ ... +x_{j-2}\). Písmenom \(E\) označme súčet všetkých nekladných čísel. Získali sme tak disjunktný rozklad postupnosti, teda každé číslo v nej prispelo do súčtu práve raz do jedného písmena. Podľa druhej podmienky v zadaní musí \(A+B+C+D+E=0\).

Všetky prvky, ktoré sú vľavo (o 1 menší index) od nekladného čísla, spĺňajú: \(x_{j-1}\le x_j+x_{j+1}\) Sčítajme takto cez všetky prvky, ktoré sú naľavo od nekladných čísel (teda aj tých samostatných). Dostaneme tak \(C+A\le E+C_n(B+A)\). Dosaďme za \(E=-A-B-C-D\), získavame \(2C\le A(C_n-2) + B(C_n-1)-D\).

Predpokladajme pre spor, že \(C_n\le 2\). Vezmime si teda jeden cyklus, kde \(x_{i}\) a \(x_{j}\) sú nekladné, a medzi nimi sú iba kladné čísla. Platia pre ne nerovnosti: \(x_{i+1}\le x_{i+2}+2x_{i+3}\). Tiež platí \(x_{i+3}\le x_{i+4}+2x_{i+5}\). Po dosadení do prvej nerovnosti získame \(x_{i+1}\le x_{i+2}+x_{i+3}+x_{i+4}+2x_{i+5}\). A znova vieme, že \(x_{i+5}\le x_{i+6}+2x_{i+7}\), dosadíme a pokračujeme rovnako až do konca cyklu, získame tak pre nepárny počet čísel v cykle \(x_{i+1}\le x_{i+2}+x_{i+3}+\dots+x_{j-3}+ 2x_{j-1}\). Pre párny počet v cykle získame iba \(x_{i+1}\le x_{i+2}+x_{i+3}+\dots+x_{j-3}+ 2x_{j-2}\), kam dosadíme nerovnosť \(x_{j-2}\le 2x_{j-1}\), ktorá platí (dokonca je ostrá, čo bude dôležité neskôr) pretože nutne musí platiť zo zadania \(x_{j-2}\le x_{j-1}\). Každopádne platí \(x_{i+1}\le x_{i+2}+x_{i+3}+\dots+x_{j-3}+ 2x_{j-1}\). Sčítajme túto nerovnosť cez všetky cykly s aspoň dvoma prvkami, získame tak \(B\le D+2C\).

Spojením \(2C\le A(C_n-2) + B(C_n-1)-D\) a \(B-D\le 2C\) získavame \(0\le (C_n-2)(A+B)\). Kedže ale \(A\), \(B\) sú nekladné čísla a nemôžu byť obe nulové, tak nutne musí byť \(C_n\ge 2\).

Na dokončenie dôkazu nám stačí ukázať, že pre nepárne \(n\) nemôže rovnosť nastať. Pre nepárne \(n\) musí byť v niektorom cykle párny počet kladných čísiel (pretože ak spojíme každý cyklus s jeho nekladným prvým číslom, tak v prípade samých nepárnych cyklov získame celkový počet čísiel párny). Uvedomme si, že na to, aby nastala rovnosť \(0=(C_n-2)(A+B)\), musí platiť rovnosť aj vo všetkých nerovnostiach, z ktorých sme ju dostali. Teda konkrétne, pre nepárne \(n\) musí platiť v cykle s párnym počtom kladných čísel aj \(x_{j-2}=2x_{j-1}\). To je ale problém, keďže z podmienky zo zadania musí platiť \(x_{j-2}\le x_{j-1}\). Tieto nerovnosti ale spolu nutne dávajú \(x_{j-2}=x_{j-1}=0\). To sme si ale na začiatku uvedomili, že nemôžu dve nekladné čísla nasledovať po sebe, preto pre nepárne \(n\) rovnosť nastať nemôže.