XXII OM - III - Zadanie 5

Zawody matematyczne:

XXII OM, 1970-1971

Etap:

III

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

$ \begin{array}{cc} a_1 + a_2 + \ldots + a_{10} < B,\\ a_{11} + a_{12} + \ldots + a_{20} < B,\\ \ldots\\ a_{91} + a_{92} + \ldots + a_{100} < B. \end{array} $

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

$ (1) \qquad A \geq 505. $

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

$ 100, 1, 99, 2, 98, 3, 97,4, \ldots, 51, 50. $

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

$ a_{2n+1} = 100 - n\ \textrm{dla}\ 0 \leq n \leq 49, $

$ a_{2n} = n\ \textrm{dla}\ 1 \leq n \leq 50. $

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

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

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

$ \begin{split} s &= a_{2k+1} + a_{2k+2} + \ldots + a_{2k+10} =\\ &= (a_{2k} + a_{2k+1} +\ldots+ a_{2k+9}) + a_{2k+10} - a_{2k} =\\ &=s + (k + 5) - k = s + 5 = 505. \end{split} $

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

$ (2) \qquad A \leq 505. $

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