Komentarz

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 $.

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

Dodaj komentarz