10. Kľoby Mi Smrdia vzorové riešenie

Majme čísla, ktoré vyhovujú zadaniu. Nech \(I\) je taká množina indexov, pre ktorú platí \(\ell_i \geq p_i\), a nech \(J\) je množina zvyšných indexov. Na začiatok si trochu upravme rovnosť v tretej podmienke zo zadania do zaujímavejšieho tvaru \[\sum_{i \in I} \ell_i - p_i = \sum_{j \in J} p_j - \ell_j,\] čiže naľavo sčítavame cez všetky dvojice, kde platí \(\ell_i \geq p_i\), napravo cez zvyšné dvojice. Hľadané maximum bude následne súčet oboch strán rovnosti \[S = \sum_{i \in I} \ell_i - p_i + \sum_{j \in J} p_j - \ell_j = \sum_{i=1}^{31}|\ell_i-p_i|.\]

Tento výraz chceme odhadnúť zhora. Všimnime si, že sumy majú rovnakú hodnotu, takže \(S\) sa nezmení keď ich rôzne naváhujeme a vhodne celý výraz predelíme. Nech \(k\) je veľkosť množiny \(I\). Naváhujme to nasledovne \[\frac{31}{2}S = (31-k)\sum_{i \in I} (\ell_i - p_i) + k \sum_{j \in J} (p_j - \ell_j).\]

Keď si predstavíme vynásobenie \(k\) ako sčítanie každého člena sumy \(k\)-krát, tak obe sumy majú rovnaký počet členov a vieme to zapísať ako jednu sumu nasledovne \[\frac{31}{2}S = \sum_{i \in I}\sum_{j \in J} (\ell_i - p_i + p_j - \ell_j).\]

No a poďme konečne odhadovať! Pre \(i>j\) máme \(p_i > p_j\) a platí \[\begin{aligned} \ell_i &\leq 4247 - (31 - i), \\ - p_i + p_j &\leq -i + j, \\ - \ell_j &\leq -j,\end{aligned}\] analogicky pre \(i<j\) máme \(\ell_i < \ell_j\) a odhady budú rovnaké, len vymeníme \(\ell\) a \(p\), preto \[\frac{31}{2}S = \sum_{i \in I}\sum_{j \in J} (\ell_i - p_i + p_j - \ell_j) \leq \sum_{i \in I}\sum_{j \in J} ([4247 - (31 - i)] + (j - i) - j) = \sum_{i \in I}\sum_{j \in J} 4216 = 4216k(31-k),\] \[S \leq 272k(31-k).\]

Už len nájsť maximum kvadratickej funkcie. Vyjde \(k=31/2\) a teda nás zaujíma \(k=15,16\). Vtedy \(S = 65\,280\).

Pre \(i \leq 16\): \(l_i = i\), pre \(j>16\): \(l_j = 4247-(31-j)\) a pre \(p_k=2040+k\) sa maximum naozaj nadobúda a tieto čisla zároveň vyhovujú zadaniu, teda maximálna hodnota je \(65\,280\).