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}.$$