XXXIX OM - III - Zadanie 1

Zawody matematyczne:

XXXIX OM, 1987-1988

Etap:

III

Liczby $x_1, x_2, \ldots, x_n$ należące do przedziału $\langle 0; 1\rangle$ spełniają warunek

$ \sum_{i=1}^n x_i = m+r, $

gdzie $m$ jest liczbą całkowitą, $r \in \langle 0; 1)$ . Dowieść, że

$ \sum_{i=1}^n x_i^2 \leq m+r^2 $

Rozwiązanie

Rozpatrzmy najpierw przypadek szczególny, gdy wszystkie liczby $x_1, \ldots, x_n$ , z wyjątkiem co najwyżej jednej, są równe $0$ lub $1$ . Skoro $x_1 + \ldots +x_n = m + r$ , $m$ całkowite, $0 \leq r < 1$ , to (w tym przypadku) dokładnie $m$ spośród liczb $x_i$ jest jedynkami, jedna równa się $r$ , a pózostałe są zerami. Tak więc $x_i^2+ \ldots +x_k^2 = m+r^2$ i warunek z tezy zadania jest spełniony.

Załóżmy teraz, że istnieją liczby $x_k, x_l \in (0; 1)\ (k \ne l)$ ; jeśli takich liczb jest więcej niż dwie, wybieramy dwie dowolne. Określamy nowy układ $(y_1, \ldots, y_n$ ) liczb z przedziału $\langle 0; 1 \rangle$ przyjmując:

$ \begin{split} y_i & = x_i \ \textrm{dla} \ i \ne k, l,\\ y_k & = [x_k+x_l],\\ y_1 & = x_k + x_l-[x_k + x_l] = x_k + x_l-y_k. \end{split} $

Suma liczb układu $(y_1, \ldots, y_n)$ jest taka sama, jak układu $(x_1, \ldots, x_n)$ , natomiast suma kwadratów jest większa:

$ \begin{split} \sum_{i=1}^n y_i^2&-\sum_{i=1}^k x_i^2 = y_k^2+y_l^2 - x_k^2 - x_l^2 =\\ &= y_k^2+(x_k + x_l-y_k)^2-x_k^2-x_l^2 =\\ &= 2y_k^2 + (x_k+x_l)^2-2(x_k+x_l)y_k-x_k^2-x_l^2 =\\ &= 2(y_k^2+x_k x_l-x_ky_k-x_ly_k) =\\ &= 2(x_k-y_k)(x_l-y_k) > 0; \end{split} $

ostatnia nierówność wynika z tego, że $y_k$ równa się $0$ lub $1$ , natomiast $x_k$ i $x_l$ są liczbami z przedziału $(0; 1)$ .

W układzie $(y_1, \ldots,y_n)$ jest mniej liczb z przedziału $(0; 1)$ niż w układzie $(x_1, \ldots ,x_n)$ (bo $y_k \in \{0, 1\}$ ). Jeśli nadal są co najmniej dwie takie liczby, możemy procedurę powtórzyć. Kontynuując to postępowanie, dojdziemy po skończenie wielu krokach do układu $(z_1, \ldots,z _n)$ , $z_i \in \langle 0; 1 \rangle$ , w którym co najwyżej jedna liczba jest różna od $0$ i $1$ . W każdym kroku suma kwadratów liczb nowego układu jest większa niż starego, natomiast suma liczb układu pozostaje niezmieniona. Wobec tego