XLIV OM - I - Zadanie 8

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

\[<br /> k_1^3 + k_2^3 + \ldots k_n^3 \leq 7n<br /> \]

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

\[<br /> k_1 = \ldots = k_\alpha > k_{\alpha+1} \geq \ldots \geq k_{\beta-1} > k_\beta = \ldots = k_n;<br /> \]

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

\[<br /> l_\alpha = k_\alpha-1, \quad l_\beta = k_\beta + 1; \quad l_i = k_i \quad \textrm{dla } i\neq \alpha, \beta.<br /> \]

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

\[<br /> \begin{split}<br /> (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=\\<br /> &=\sum_{i=1}^{n} k^3_i- 3k_\alpha^2+3k_\alpha-1 +3k_\beta^2+3k_\beta+1=\\<br /> &=\sum_{i=1}^{n} k^3_i- 3(k_\alpha+k_\beta)(k_\alpha-k_\beta-1) \leq\\<br /> &\leq 7n - 3(k_\alpha+k_\beta)(k_\alpha-k_\beta-1) \leq 7n;<br /> \end{split}<br /> \]

ponadto, oczywiście,

\[<br /> (2) \qquad \sum_{i=1}^{n} l_i=\sum_{i=1}^{n} k_i<br /> \]

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ć

\[<br /> (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\}.<br /> \]

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

\[<br /> (4) \qquad 7n \geq m(c + 1)^3 + (n-m)c^3 = m(3c^2 + 3c + 1) + nc^3,<br /> \]

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

\[<br /> s = m(c +1) + (n - m)c = nc + m,<br /> \]

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ść

\[<br /> 7\sum_{i=1}^n k_i \leq \sum_{i=1}^n(k_i^3 + 6) \leq 7n + 6n = 13n.<br /> \]

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

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

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:

\[<br /> \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;<br /> \]

suma tak określonych liczb $ k_i $ wynosi

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

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

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Komentarze

Dodaj nową odpowiedź