Optymalizacja nierówności

[krazi225]

Kiedyś na warsztatach przed olimpiadą spoktałem się z takim zadaniem, ale nie zobaczyłem rozwiązania, a wydało mi sie dość ciekawe.
Dla ustalonego n wyznacz największą wartość sumy liczb całkowitych \(\displaystyle{ x _{1},x_{2},...,x_{n}}\) spełniających warunek: \(\displaystyle{ x_{1} ^{4}+x_{2}^{4}+...+x_{n}^{4} \le 29n}\).
Wydaje mi się sensowne że każda z liczb będzie równa 2 i suma 2n, ale nie jestem pewien jak to udowodnić. Czy jest jakiś sposób na tego typu zadania?

[Zahion]

Wydaje mi się sensowne że każda z liczb będzie równa 2 i suma 2n, ale nie jestem pewien jak to udowodnić.

Poprawną odpowiedzią będzie \(\displaystyle{ \left[ \frac{11n}{5} \right]}\)
Jeżeli dalej nie będziesz wiedział jak do tego dojść to napisz.

[krazi225]

A rzeczywiście pasuje, dzięki. Czyli rozumiem to tak, że ustalamy sobie za kazde \(\displaystyle{ x _{i}}\) przynajmniej 2, a ten odsetek jaki zostanie po zmaksymalizowaniu oznaczam jako b. Wtedy \(\displaystyle{ 16n+b \le 29n}\), czyli
\(\displaystyle{ b \le 13n}\) i dla \(\displaystyle{ n=5k, 13n=65k=(81-16)k}\), więc dla n podzielnych przez 5 odsetek mozemy zerować i suma zwiększa się o 1. Czy tyle wystarczy?

[Zahion]

Tak, ale wymaga to wszystko uzasadnienia.
Po pierwsze dlaczego nie działamy na liczbach większych niż \(\displaystyle{ 3}\).
Weźmy \(\displaystyle{ x_{1} \le ... \le x_{n}}\). Załóżmy, że \(\displaystyle{ x_{n} \ge 4}\).
Łatwo udowodnić, że \(\displaystyle{ \left( x_{1} + 1\right)^{4} + \left( x_{n} - 1\right)^{4} < x_{1}^{4} + x_{n}^{4}}\), natomiast \(\displaystyle{ \sum_{i=1}^{n}x_{i} = \left( x_{1} + 1\right) + \sum_{i=2}^{n-1} + \left( x_{n} - 1 \right)}\).
Pokazuje to, że nie warto rozpatrywać w tej reszcie liczb większych niż \(\displaystyle{ 3}\), ponieważ można zachować sumę liczb i zmniejszyć wartość sumy czwartych potęg.
Jeżeli natomiast możemy skonstruować taki ciąg z liczb \(\displaystyle{ 2, 3}\), bez wykorzystywania \(\displaystyle{ 1}\) - dlaczego jej nie wykorzystujemy ? - to otrzymamy największą możliwą wartość sumy.

Najprościej jest to natomiast ugryźć z (nie)równości \(\displaystyle{ 0 \le \left( x-2\right)\left( x-3\right)\left( x^{2}+5x+19\right) = x^{4} -65x + 114}\)
Mamy wtedy, że \(\displaystyle{ 65x_{i} \le \sum_{i=1}^{n}\left( x_{i}^{4} +114\right) \le 29n + 114n = 143n}\), więc \(\displaystyle{ \sum_{i=1}^{n}x_{i} \le \left[ \frac{143n}{65} \right] = \left[ \frac{11n}{5} \right]}\) i skonstruować ciąg, który osiąga tą wartość.
Odpowiedzieć natomiast należy jeszcze na pytanie - dlaczego nie rozpatrujemy w tym wypadku możliwości włożenia gdzieś liczby \(\displaystyle{ 1}\) ?
Jeżeli ktoś zastanawia się nad tym skąd pojawiła się ta równość - Otóż szukamy takiego wielomianu \(\displaystyle{ W(x)}\), który zeruje się dla \(\displaystyle{ x = 2, x = 3}\) (zakładamy, że właśnie ten układ optymalizuje Naszą sumę) i jest postaci \(\displaystyle{ W(x) = x^{4} + ax + b}\). Wtedy jesteśmy w stanie uzależnić, właśnie od tego "optymalnie" wybranego przez Nas układu wartości \(\displaystyle{ x_{i}^{4}}\) i \(\displaystyle{ x_{i}}\). Wynika stąd, że szukamy wielomianu postaci \(\displaystyle{ W(x) = \left( x-2\right)\left( x-3\right)\left( x^{2} +cx + d \right)}\) i dobieramy wartości \(\displaystyle{ c, d}\) tak, aby zerować współczynniki przy potęgach \(\displaystyle{ x^{3}, x^{2}}\).

[krazi225]

Bardzo porządne rozwiązanie z tym wielomianem. Co do 4 i 1 to ja to sobie tłumaczyłem tak że \(\displaystyle{ 4 ^{4} > 3 \cdot 3 ^{4}}\), dlatego bardziej opłaca się zamienić 4 na aż trzy trójki. A jak wiemy już, że czwórki w tym ciągu nie będzie to przy ustalonej sumie każdej jedynce musiałaby odpowiadać jedna trójka. A ponieważ \(\displaystyle{ 2 \cdot 2 ^{4}<1+3 ^{4}}\), to lepiej każdą z tych par zastąpić dwiema dwójkami.