XXII OM - III - Zadanie 5

Znaleźć największą liczbą całkowitą $ A $ taką, że dla każdej permutacji zbioru liczb naturalnych nie większych od 100 suma pewnych 10 kolejnych wyrazów jest co najmniej równa $ A $.

Rozwiązanie

Suma wszystkich liczb naturalnych nie większych od $ 100 $ jest równa $ 1 + 2 + \ldots + 100 = \frac{1 +100}{2} 100 = 5050 $. Jeżeli $ a_1, a_2, \ldots, a_{100} $ jest pewną permutacją zbioru liczb naturalnych nie większych od $ 100 $ i suma każdych $ 10 $ wyrazów tej permutacji jest mniejsza od pewnej liczby $ B $, to w szczególności

\[<br />
\begin{array}{cc}<br />
a_1    + a_2    + \ldots + a_{10} < B,\\<br />
a_{11} + a_{12} + \ldots + a_{20} < B,\\<br />
\ldots\\<br />
a_{91} + a_{92} + \ldots + a_{100} < B.<br />
\end{array}<br />
\]

Dodając te nierówności stronami otrzymujemy, że $ a_1 + a_2 + \ldots + a_{100} = 1 + 2 + \ldots + 100 < 10B $, czyli $ 505 < B $.

Zatem określona w zadaniu liczba $ A $ spełnia nierówność.

\[<br />
(1) \qquad  A \geq 505.<br />
\]

Z drugiej strony rozważmy następującą permutację $ a_1, a_2,\ldots, a_{100} $ zbioru liczb naturalnych nie większych od $ 100 $

\[<br />
100, 1, 99, 2, 98, 3, 97,4, \ldots, 51, 50.<br />
\]

Permutację tę można określić wzorami:

\[<br />
a_{2n+1} = 100 - n\ \textrm{dla}\ 0 \leq n \leq 49,<br />
\]
\[<br />
a_{2n}   = n\ \textrm{dla}\ 1 \leq n \leq 50.<br />
\]

Udowodnimy, że suma dowolnych kolejnych $ 10 $ wyrazów tej permutacji jest nie większa od $ 505 $.

Istotnie, jeżeli pierwszy z rozważanych $ 10 $ wyrazów ma numer parzysty $ 2k $, to

\[<br />
\begin{split}<br />
s &= a_{2k} + a_{2k+1} + \ldots + a_{2k+9} =\\<br />
&= (a_{2k} + a_{2k+2} +\ldots+ a_{2k+8}) + (a_{2k+1} + a_{2k+3} + \ldots + a_{2k+9}) =\\<br />
&=<br />
[k + (k + 1) + \ldots + (k + 4)] + \{(100 - k) +\\<br />
&\quad+ [100 - (k + 1)] + \ldots + [100 - (k + 4)]\} = 500.<br />
\end{split}<br />
\]

Jeżeli zaś pierwszy z rozważanych wyrazów ma numer nieparzysty $ 2k + 1 $, to

\[<br />
\begin{split}<br />
s &= a_{2k+1} + a_{2k+2} + \ldots + a_{2k+10} =\\<br />
&= (a_{2k} + a_{2k+1} +\ldots+ a_{2k+9}) + a_{2k+10} - a_{2k} =\\<br />
&=s + (k + 5) - k = s + 5 = 505.<br />
\end{split}<br />
\]

Tak więc suma dowolnych $ 10 $ kolejnych wyrazów tej permutacji jest nie większa od $ 505 $. Wobec tego liczba $ A $ określona w zadaniu spełnia nierówność

\[<br />
(2) \qquad  A \leq 505.<br />
\]

Z (1) i (2) wynika, że $ A = 505 $.

Uwaga 1. Zadanie można uogólnić następująco: Znaleźć największą liczbę całkowitą $ A $ taką, że dla każdej permutacji zbioru liczb naturalnych nie większych od liczby parzystej $ n = 2t $ suma pewnych $ m = 2r $ (gdzie $ r $ jest dzielnikiem $ t $) kolejnych wyrazów jest co najmniej równa $ A $.

Dokonując drobnych zmian w podanym wyżej rozwiązaniu polegających na zamianie liczby $ 100 $ przez $ 2t $, a liczby $ 10 $ przez $ 2r $, można dowieść, że $ A =  \frac{1}{2} m(n + 1) $.

Uwaga 2. W przypadku gdy $ m \leq n $ są dowolnymi liczbami naturalnymi na ogół nie jest prawdą, że każda permutacją zbioru liczb naturalnych nie większych od $ n $ zawiera $ m $ kolejnych wyrazów o sumie nie mniejszej od $  \frac{1}{2} m(n + 1) $. Na przykład przy $ n = 6 $, $ m = 4 $ permutacja $ 6, 4, 1, 2, 3, 5 $ nie zawiera czterech kolejnych wyrazów o sumie nie mniejszej od $ 14 $.

Komentarze

Dodaj nową odpowiedź