LII OM - I - Zadanie 12

Zawody matematyczne:

LII OM, 2000-2001

Etap:

Rozpatrujemy ciągi liczb całkowitych $x_0,x_1,\ldots,x_{2000}$ spełniające warunki

$ x_0 = 0\ \textrm{oraz}\ |x_n| = |x_{n-1} + 1| \ \textrm{dla}\ n = 1,2,\ldots,2000. $

Znaleźć najmniejszą wartość wyrażenia $|x_1 + x_2 +\ldots + x_{2000}|$ .

Rozwiązanie

Odpowiedź: Najmniejsza wartość danego wyrażenia wynosi $12$ .

Wykażemy indukcyjnie, że dla dowolnego ciągu $(x_n)$ spełniającego warunki zadania zachodzi równość

$ (1)\qquad x_0 + x_1 + x_2 + \ldots + x_n = \frac{1}{2} (x_n^2 + 2x_n-n) \quad (n = 0,1,2,3,\ldots,2000). $

Dla $n = 0$ obie strony powyższej równości są równe $0$ . Załóżmy więc, że zależność (1) jest prawdziwa dla pewnego $n$ . Wówczas

$ \begin{split} x_{0}+x_{1}+x_{2}+\ldots+x_{n}+x_{n+1}=\frac{1}{2}(x_{n}^{2}+2x_{n}-n)+x_{n+1}=\\ \qquad =\frac{1}{2}((x_{n}+1)^{2}-(n+1))+x_{n+1}=\frac{1}{2}(x_{n+1}^{2}-(n+1))+x_{n+1}=\\ \qquad =\frac{1}{2}(x_{n+1}^{2}+2x_{n+1}-(n+1)), \end{split} $

co kończy dowód indukcyjny wzoru (1).

Zatem

$ |x_{1}+x_{2}+\ldots+x_{2000}|=\frac{1}{2}|x_{2000}^{2}+2x_{2000}-2000|=\frac{1}{2}|(x_{2000}+1)^{2}-2001|. $

Liczbą kwadratową leżącą najbliżej liczby $2001$ jest $2025 = 45^2$ . Stąd oraz z powyższej równości wnioskujemy, że wyrażenie $|x_1 + x_2 +\ldots + x_{2000}|$ nie może przyjąć wartości mniejszej niż $\frac{1}{2}|2025 - 2001| =12$ .

Pozostaje zauważyć, że wartość $12$ można zrealizować przyjmując

$ x_n=\left\{\begin{array}{rl} n&\textrm{dla}\ n \leq 44;\\ -45&\textrm{dla}\ n > 44, n\ \textrm{nieparzyste};\\ 44&\textrm{dla}\ n > 44, n\ \textrm{parzyste}. \end{array}\right. $

Powyższy ciąg spełnia warunki zadania. Ponadto $x_{2000} = 44$ , co na mocy równości (1) daje $|x_1 + x_2 +\ldots + x_{2000}| = 12$ .