8. Kričiaca Mnohodetná Skupina vzorové riešenie

Našou úlohou je nájsť číslo \(k\), pre ktoré platí nerovnosť zo zadania, budeme ju označovať ako \((\star\)). Za \(k\) si môžeme vyberať z čísel \(1,\, 2,\,\dots,\, n\). Môžeme si všimnúť, že pri zmene \(k\) sa výraz na ľavej strane nemení (je to vždy to isté číslo), zatiaľ čo na pravej strane sa výraz môže meniť. Ak nerovnosť \((\star\)) platí pre nejaké \(k\), tak určite platí aj pre také \(m\), pre ktoré je súčet \(|a_1 + a_2 + \dots + a_m|\) najväčší možný. Preto hľadanie \(k\) vybavíme hneď na začiatku a budeme dokazovať nerovnosť \((\star)\) pre \(k = m\). Ale ako na to?

Často použiteľný spôsob, ako sa dajú dokazovať nerovnosti, je postupné upravovanie jednej strany nerovnosti na ďalšie výrazy, medzi ktorými platí správna nerovnosť. Na ľavej strane máme v absolútnej hodnote súčet čísel. Pri takýchto prípadoch príde vhod nerovnosť \(|x + y| \le |x| + |y|\) (pre reálne čísla \(x\), \(y\)), ktorú možno ľahko dokázať a taktiež aj zovšeobecniť pre súčet \(n\) čísel. Takto vieme dostať súčet výrazov \(|a_ib_i|\), resp. \(|a_i|b_i\) vďaka nezápornosti \(b_i\). Avšak z takýchto výrazov ťažko získame späť súčet \(|a_1 + a_2 + \dots + a_m|\).

Ďalším nedostatkom je, že zatiaľ nevyužívame voľbu \(k=m\). Táto voľba nám dáva totiž veľa nerovností, ktoré môžeme využiť. Tieto nerovnosti sa týkajú súčtov \(|a_1 + a_2 + \dots + a_i|\), aby sa nám s nimi ľahšie pracovalo, označíme si \(s_i = a_1 + a_2 + \dots + a_i\) pre celé čísla \(1 \le i \le n\). Tak budeme mať na pravej strane v absolútnej hodnote len jednu neznámu a k nej sa už dopracujeme ľahšie.

Teraz si však musíme premenné \(a_1,\, a_2,\, \dots,\, a_n\) vyjadriť pomocou \(s_1,\, s_2\, \dots,\, s_n\). Zjavne \(a_1 = s_1\), potom \(a_2 = s_2 - s_1\) a všeobecne \(a_i = s_i - s_{i-1}\) pre \(2 \le i \le n\). Ľavú stranu si vieme teda zapísať ako Teraz môžeme súčet v absolútnej hodnote odhadnúť súčtom absolútnych hodnôt, ako sme spomenuli vyššie.

Vďaka podmienke \(b_{i} \ge b_{i+1}\) sú rozdiely \(b_{i} - b_{i+1}\) nezáporné. Preto ich môžeme vybrať z absolútnych hodnôt, čím dostaneme \[|(b_1 - b_2)s_1| + \dots + |(b_{n-1} - b_n)s_{n-1}| + |b_ns_n| = (b_1 - b_2)|s_1| + \dots + (b_{n-1} - b_n)|s_{n-1}| + b_n|s_n|.\]

Je na čase využiť, že \(m\) sme si zvolili tak, že hodnota \(|s_m|\) je najväčšia spomedzi \(|s_i|\), platí \(|s_i| \le |s_m|\). Vďaka nezápornosti \(b_i - b_{i+1}\) platí aj \((b_i - b_{i+1})|s_i| \le (b_i - b_{i+1})|s_m|\). Získavame tak ďalší vzťah

Nakoniec nám stačí využiť, že \(b_1 \le 1\), a preto \(b_1|s_m| \le |s_m|\). Spojením všetkých nerovností, prípadne rovností, cez ktoré sme prešli, dostávame \[|a_1b_1 + a_2b_2 + \dots + a_nb_n| \le |s_m|,\] čo sme mali ukázať.