9. Komplikáciu Má Shinji vzorové riešenie

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)\) má \(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}.\]