Zadanie

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ápis1 čí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ť.


  1. binárny zápis je postupnosť \(0\) a \(1\) začínajúca \(1\) okrem prípadu, kedy \(f(x) = 0\)↩︎

Na začiatok uvedieme nejakú tú analýzu problému, kde uchopiť takéto problémy. Pozrieme sa na správanie funkcie \(f\) pri malých hodnotách \(n\). Funkcia \(f\) nám dáva hodnoty \(0,1,0,3,2,1,0,7,6,5,4,\dots\) pre čísla \(n\in \{1,2,3,\dots \}\). Spravíme niekoľko pozorovaní: Platí nerovnosť \(f(n)<n\), nakoľko prvá binárna cifra \(n\) sa zmení na nulu v \(f(n)\) a pred ňou budú iba nuly. Číslo \(2^k-1\) má v binárnej sústave samé jednotky, a teda \(f(2^k-1)=0\). Taktiež číslo \(2^k\) vyzerá v binárnom zápise \(100\dots00\), kde \(k\) je počet núl, potom \(f(2^k)\)\(k\) jednotiek vo svojom zápise. Ďalej si uvedomme, že pre ľubovoľné \(n\) je číslo \(f(n)\otimes n = 0\), kde \(\otimes\) je binárny xnor. Operácia xnor robí to, že si zoberie dve cifry (v binárnom zápise) a vyhodí \(1\) ak sú rovnaké a \(0\) ak sú rôzne. To platí, presne preto, že sme si funkciu \(f(n)\) zadefinovali, že obracia cifry \(n\). Pre číslo \(n\) tvaru \(2^k + l\), kde \(0\leq l<2^k\) je podmienka \(f(n)\otimes n = 0\) ekvivalentná \(f(2^k+l)\otimes (2^k + l)=0\). Rovnosť \(2^k -l -1 \otimes 2^k +l = 0\) necháme ako cvičenie pre čitateľa. Keďže \(2^k - l- 1\) je jediné riešenie rovnice \(x\otimes 2^k +l\) menšie ako \(2^k\), tak musí platiť, že \(f(n) = 2^k - 1 - l\).

Uvedieme dve riešenia. Prvé priamočiare, vyžadujúce iba trochu vytrvalosti a narábanie so sumami na úrovni geometrických a aritmetických súm a hľadania maxima kvadratickej funkcie, a druhé s trochou nápadu. Poznatky z prvého odseku budeme využívať v oboch riešeniach.

Priamočiare riešenie

Súčet \(f(1)+f(2)+\dots+f(n)\) spočítame priamo, rozdelíme ho na niekoľko ucelených častí od \(2^k-1\) po \(0\) a zvyšok. Od \(2^{i-1}\) po \(2^i-1\) máme súčet \[2^{i-1}-1 + 2^{i-1}-2 + \dots + 1 + 0 = \frac{(2^{i-1}-1)2^{i-1}}{2}=(2^{i-1}-1)2^{i-2}.\] Nech teda \(n=2^k +l\), súčet po \(2^k\) bude \[\sum_{i=2}^{k} (2^{i-1}-1)2^{i-2} = \sum_{i=2}^{k} 2^{2i-3}-2^{i-2} = \sum_{i=2}^{k} 2^{2i-3}- \sum_{i=2}^{k} 2^{i-2} = \sum_{i=0}^{k-2} 2^{2i+1}- \sum_{i=0}^{k-2} 2^{i}.\] To sú geometrické rady a tie vieme sčítať,

\[\begin{aligned} \sum_{i=0}^{k-2} 2^{2i+1} &= 2\cdot \frac{4^{k-1}-1}{4-1}=\frac{2}{3}(4^{k-1}-1), \\ \sum_{i=0}^{k-2} 2^{i} &= \frac{2^{k-1}-1}{2-1}=2^{k-1}-1, \\ \sum_{i=0}^{k-2} 2^{2i+1}- \sum_{i=0}^{k-2}2^{i} &=\frac{2}{3}(4^{k-1}-1)-(2^{k-1}-1).\end{aligned}\]

Zvyšok od \(2^k\) po \(n=2^k+l\) je vlastne \[\sum_{i=0}^{l} 2^k -1-i = (l+1)\cdot( 2^k) - \frac{(l+1)(l+2)}{2}.\]

Dokopy teda súčet \[\sum_{i=1}^{n} f(i) = \frac{2}{3}(4^{k-1}-1)-(2^{k-1}-1) + (l+1)\cdot( 2^k) - \frac{(l+1)(l+2)}{2}.\]

Na pravej strane dokazovanej nerovnosti máme \[\frac{n^2}{4} = \frac{(2^k+l)^2}{4} = \frac{2^{2k}+2\cdot2^k\cdot l +l^2}{4}.\]

Dokazujeme teda nerovnosť \[\frac{2}{3}(4^{k-1}-1)-(2^{k-1}-1) + (l+1)\cdot( 2^k) - \frac{(l+1)(l+2)}{2} \leq \frac{2^{2k}+2\cdot2^k\cdot l +l^2}{4},\]

\[-\frac{2}{3} + 2^{k-1}(l+1) - \frac{3l^2}{4}-\frac{3l}{2} \leq \frac{1}{3}4^{k-1},\]

\[3\cdot 2^{k+1}(l+1) - (9l^2+18l+8) \leq 4^{k}.\]

Pravá strana nezávisí od \(l\) ľavá áno. Preto by bolo fajn keby sme sa pozreli akú maximálnu hodnotu môže výraz naľavo nadobúdať ak nehýbeme \(k\)-čkom. Funkcia na ľavo je konkávnou kvadratickou funkciou, nakoľko pri \(l^2\) je znamienko mínus. Vzorec na výpočet vrcholu paraboly \(ax^2+bx+c\) je následujúci \(x=-\frac{b}{2a}\). Tento všeobecný vzorec sa dá odvodiť, keď máme korene, pomerne jednoducho. Tento vzorec platí aj keby sme mali parabolu bez koreňov. Pre fajnšmekrov z derivácie ľahko vidieť, že \(ax^2+bx+c \frac{d}{dx} = 2ax+b = 0\) je rovnicou maxima s riešením \(x = -\frac{b}{2a}\). Preto \(l_{max} = \frac{2^{k}}{3}-1\). Lenže číslo \(\frac{2^{k}}{3}-1\) očividne nie je celé číslo, preto najbližšie celé číslo je buď \(\frac{2^{k}}{3}-1-\frac 13\) alebo \(\frac{2^{k}}{3}-1 + \frac 13\), v závislosti od \(k\). Jedno z týchto čísel bude celé a preň parabola dosahuje svoje maximum na celých číslach.

Dosadením maxima na celých číslach \(l_{max} \pm \frac 13\) máme \[3\cdot 2^{k+1}\left(\frac{2^{k}}{3}\pm \frac 13\right ) - \left(9\left(\frac{2^{k}}{3}-1\pm \frac 13\right )^2+18\left(\frac{2^{k}}{3}-1 \pm \frac 13\right)+8\right) \leq 4^{k},\]

\[2^{2k+1} \pm 2^{k+1}-\left(9\left(\frac{2^{k}}{3}-1\pm \frac 13 \right)^2+18\left(\frac{2^{k}}{3}-1\pm \frac 13 \right) +8\right) =\]

\[2\cdot 4^k \pm 2^{k+1} - 9\left(\frac{4^k}{9} +1 +\frac{1}{9} -2 \cdot \frac{2^k}{3} \pm 2\cdot \frac{2^k}{9} \mp 2 \cdot \frac{1}{3} \right) - 18\left( \frac{2^k}{3} -1 \pm \frac{1}{3}\right) - 8 =\] \[= 2\cdot 4^k -4^k -9-1+6\cdot 2^{k} \pm 6 - 6\cdot 2^k + 18 \mp 6 -8 = 4^k \leq 4^k\]

Dokázali sme teda nerovnosť zo zadania. Ba čo viac, našli sme aj kedy nastáva rovnosť. Pre \(n= 2^k + \frac{2^k\pm 1}{3}-1\) nastáva rovnosť.

Riešenie s nápadom

Postupujme matematickou indukciou. Pre \(n=1\) tvrdenie zjavne platí. Zoberme znovu \(n=2^k+l\), kde \(l < 2^k\). Rozlíšime dva prípady. Ak \(l < 2^{k-1}\), tak

\[f(1)+\dots+f(n-1)+f(2^k+l)\leq \frac{(n-1)^2}{4}+f(2^k+l)=\frac{(n-1)^2}{4}+2^k-l-1 < \frac{(n-1)^2}{4}+2^k-2^{k-1}-1=\] \[= \frac{(n-1)^2}{4} +2^{k-1}-1 \leq \frac{(n-1)^2}{4}+\frac{n}{2}-1=\frac{n^2-3}{4} < \frac{n^2}{4}.\]

V prípade \(l \geq 2^{k-1}\) nebude stačiť použiť indukciu s krokom o \(1\), ale využijeme, že indukčný predpoklad platí pre všetky menšie hodnoty od \(n\). Celý súčet si rozdelíme na dve časti. Prvá časť bude po \(t=2^k-l-2\), čo si označíme \(F(t)=f(1)+\dots+f(t)\). Druhá časť je od \(t+1\) do \(n\). Následne si funkčné hodnoty šikovne popárujeme, aby to pekne vyšlo,

\[f(1)+\dots+f(t)+f(2^k-l-1)+ \dots +f(2^k+l)=F(t)+\sum_{i=0}^{l}f(2^k-1-i)+\sum_{i=0}^{l}f(2^k+i)=\] \[F(t)+\sum_{i=0}^{l}f(2^k-1-i)+f(2^k+i)=F(t)+\sum_{i=0}^{l}(i)+(2^k-1-i)=F(t)+(l+1)(2^k-1)=\] \[F(t)+\frac{(n-t)}{2}\frac{(n+t)}{2} \leq \frac{t^2}{4}+\frac{n^2-t^2}{4}=\frac{n^2}{4}.\]

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.