XLIV OM - I - Zadanie 8

Zawody matematyczne:

XLIV OM, 1992-1993

Etap:

Dla ustalonej liczby naturalnej $n \geq 2$ wyznaczyć maksymalną wartość sumy liczb naturalnych $k_1, k_2, \ldots , k_n$ spełniających warunek

$ k_1^3 + k_2^3 + \ldots k_n^3 \leq 7n $

Rozwiązanie

Sposób I

Weźmy pod uwagę dowolny układ $(k_1,\ldots,k_n)$ liczb naturalnych spełniających podany warunek; można założyć, że $k_1 \geq \ldots \geq k_n$ . Przypuśćmy, że $k_1 - k_n \geq 2$ . Załóżmy, że w ciągu $(k_1, \ldots ,k_n)$ jest $\alpha$ liczb równych $k_1$ oraz jest $n - \beta + 1$ liczb równych $k_n$ . To znaczy, załóżmy, że

$ k_1 = \ldots = k_\alpha > k_{\alpha+1} \geq \ldots \geq k_{\beta-1} > k_\beta = \ldots = k_n; $

jeśli tylko jeden wyraz ma wartość maksymalną, wówczas $\alpha = 1$ ; jeśli tylko jeden wyraz ma wartość minimalną, wówczas $\beta = n$ . (Może też się zdarzyć, że $\alpha = \beta - 1$ ; tak jest w przypadku, gdy każdy wyraz jest równy albo maksymalnemu albo minimalnemu.)

Określamy nowy układ $(l_1, \ldots , l_n)$ , przyjmując

$ l_\alpha = k_\alpha-1, \quad l_\beta = k_\beta + 1; \quad l_i = k_i \quad \textrm{dla } i\neq \alpha, \beta. $

Układ $(l_1,\ldots,l_n)$ też spełnia podany warunek:

$ \begin{split} (1) \qquad \sum_{i=1}^{n} l_i^3 &= \sum_{i=1}^{\alpha-1} k^3_i+(k_\alpha-1)^3 + \sum_{i=\alpha+1}^{\beta-1} k^3_i+(k_\beta+1)^3 +\sum_{i=\beta+1}^{n} k^3_i=\\ &=\sum_{i=1}^{n} k^3_i- 3k_\alpha^2+3k_\alpha-1 +3k_\beta^2+3k_\beta+1=\\ &=\sum_{i=1}^{n} k^3_i- 3(k_\alpha+k_\beta)(k_\alpha-k_\beta-1) \leq\\ &\leq 7n - 3(k_\alpha+k_\beta)(k_\alpha-k_\beta-1) \leq 7n; \end{split} $

ponadto, oczywiście,

$ (2) \qquad \sum_{i=1}^{n} l_i=\sum_{i=1}^{n} k_i $

oraz zachodzą nierówności $l_1 \geq \ldots \geq l_n$ .

Jeżeli w ciągu $(k_1, \ldots , k_n)$ były co najmniej dwa wyrazy maksymalne oraz co najmniej dwa wyrazy minimalne, to zarówno blok wyrazów maksymalnych, jak i blok wyrazów minimalnych, ulega skróceniu o jedną pozycję, gdy ciąg $(k_1, \ldots,k_n)$ zastąpimy ciągiem $(l_1,\ldots,l_n)$ . Modyfikujemy teraz w analogiczny sposób układ $(l_1,\ldots,l_n)$ ; to samo robimy z otrzymanym układem, i tak dalej. W skończonej liczbie kroków uzyskamy układ z jednym tylko wyrazem maksymalnym lub z jednym tylko wyrazem minimalnym. Wartości tych wyrazów nadal są równe $k_1$ oraz $k_n$ - te same, co w wyjściowym układzie $(k_1, \ldots, k_n)$ .

Kolejne powtórzenie tej samej operacji da w wyniku nowy układ (nierosnący ciąg długości $n$ ), którego największy wyraz jest o $1$ mniejszy od $k_1$ lub najmniejszy wyraz jest o $1$ większy od $k_n$ (zmiana o $1$ może też nastąpić ,,na obu końcach''). W ten sposób różnica między największym wyrazem i najmniejszym wyrazem zmniejszy się o $1$ lub o $2$ .

Kontynuujemy to postępowanie tak długo, aż dojdziemy do układu, w którym różnica między wyrazem największym i najmniejszym nie przekracza 1. Otrzymany układ ma postać

$ (3) \qquad (\underbrace{c +1,\ldots,c+1}_m, \underbrace{c,\ldots,c}_{n-m}); \quad c \textrm{ naturalne}, \ m \in \{0,1,\ldots,n\}. $

W każdym kroku tej procedury uzyskiwaliśmy układ $n$ liczb, których suma sześcianów nie przekraczała $7n$ ; sama zaś suma liczb w układzie w ogóle nie ulegała zmianie (wzory (1) i (2)).

Ponieważ wystartowaliśmy od dowolnego dopuszczalnego układu liczb $(k_1,\ldots,k_n)$ , w którym $k_1 - k_n \geq 2$ , zatem wystarczy ograniczyć rozważania do układów postaci (3). Warunek ,,suma sześcianów $\leq 7n$ '' daje dla takiego układu oszacowanie

$ (4) \qquad 7n \geq m(c + 1)^3 + (n-m)c^3 = m(3c^2 + 3c + 1) + nc^3, $

wobec czego $c \leq 1$ . Suma wyrazów wynosi

$ s = m(c +1) + (n - m)c = nc + m, $

co jest większe dla $c = 1$ niż dla $c = 0$ . Wystarczy więc rozważać układy (3), w których $c = 1$ , czyli układy złożone z jedynek i dwójek; przy tym $m$ (liczba dwójek) ma spełniać warunek (4), który dla $c = 1$ przybiera po prostu postać $7n \geq 7m + n$ , czyli $m \leq [6n/7]$ . (Jak zwykle, symbol $[x]$ oznacza największą liczbę całkowitą, nie większą od $x$ .) A zatem szukana wartość sumy $s = n + m$ nie przekracza $n + [6n/7] = [13n/7]$ . Równość $s = [13n/7]$ uzyskamy dla układu $n$ liczb, w którym jest $m = [6n/7]$ dwójek oraz $n-m$ jedynek.

Wobec wcześniejszych spostrzeżeń, liczba $[13n/7]$ jest maksymalną możliwą do uzyskania wartością sumy $n$ liczb naturalnych, których suma sześcianów nie przekracza $7n$ .

Sposób II

Przyjmijmy, że liczby naturalne $k_i,\ldots,k_n$ spełniają podany warunek. Dla $i = 1,\ldots,n$ mamy $k_i^3 - 7k_i + 6 = (k_i - 1)(k_i - 2)(k_i + 3) \geq 0$ , czyli $7k_i \leq k_i^3 + 6$ . Dodając te $n$ nierówności stronami i uwzględniając przyjęte założenie $( k_1^3 +\ldots + k_n^3 \leq 7n)$ otrzymujemy zależność

$ 7\sum_{i=1}^n k_i \leq \sum_{i=1}^n(k_i^3 + 6) \leq 7n + 6n = 13n. $

Zatem suma $k_1 + \ldots + k_n$ , jako liczba naturalna, spełnia nierówność

$ (5) \qquad \sum_{i=1}^n k_i \leq [13n/7]. $

Weźmy teraz pod uwagę układ $(k_1,\ldots,k_n)$ składający się z $m$ dwójek oraz $n-m$ jedynek, gdzie $m = [6n/7]$ . Układ ten spełnia postulowany w zadaniu warunek:

$ \sum_{i=1}^n k_i^3 = (n-m)\cdot 1^3 + m\cdot 2^3 = n + 7m \leq n + 7\cdot(6n/7) = 7n; $

suma tak określonych liczb $k_i$ wynosi

$ \sum_{i=1}^n k_i = (n-m)\cdot 1 + m\cdot 2 = n + m = n + [6n/7] = [13n/7], $

a więc nierówność (5) staje się w tym przypadku równością. Stąd wynika, że poszukiwane maksimum wynosi $[13n/7]$ .