9. Komplikáciu Má Shinji

Keď dojedli, spokojne sa opreli vo svojich isu a uvoľnili si opasky. „Dočuj,“ povedal Jótaró. „Pomohol by si mi ešte s jedným problémom? Ak mi dáš pomocnú ruku, za odmenu ti prezradím zmysel života.“ Kubko poomáľal jeho ponuku na jazyku a nakoniec prikývol.

Sadli teda do Jótarovho auta a odviezli sa do akejsi podzemnej futuristickej základne. Všade monitory, herné konzoly, počítače, autá Nissan a hlavne rad obrovských robotov. „Problém je v tom, že nevieme dostať Shinjiho do robota,“ vysvetlil Jótaró. „On je totiž trošku divný a má takú podmienku, ktorú treba splniť, aby vstúpil do robota. Ja by som chcel vedieť, ktoré z týchto robotov podmienke vyhovujú. Tiež mi rovno pomôž niečo Shinjimu dokázať.“

Roboty sú číslované zaradom \(1\), \(2\), \(3\)…. Shinji si vymyslel špeciálnu funkciu \(f(x)\), ktorá zoberie binárny zápis¹ čísla \(x\), vymení všetky jednotky za nuly a naopak, a prevedie výsledok do desiatkového zápisu, čo je jej funkčná hodnota pre \(x\). Napríklad \(f(23)=8\), lebo \(23=10111_2\), teda \(f(23)=01000_2=8_{10}\). Shinji potrebuje, aby ste dokázali, že pre každé kladné celé \(n\) platí nerovnosť \[f(1)+f(2)+\dots + f(n)\leq \frac{n^2}{4}\] Dokážte, že Shinjiho nerovnosť platí pre každé kladné celé číslo \(n\), a následne zistite, pre ktoré \(n\) platí rovnosť.