LX OM - III - Zadanie 4

Zawody matematyczne:

LX OM, 2008-2009

Etap:

III

Niech $x_1,x_2,\cdots ,x_n$ będą liczbami nieujemnymi, których suma wynosi 1. Udowodnić, że istnieją
liczby $a1,a2,\cdots ,an \in \{0, 1, 2, 3, 4\}$ takie, że $(a_1,a_2,\cdots ,a_n) \neq (2, 2,\cdots , 2)$ oraz

$ 2 \leqslant a_1x_1 + a_2x_2 + \cdots + a_nx_n \leqslant 2+ \frac{2}{3^n-1}. $

Rozwiązanie

Rozważmy wszystkie możliwe ciągi $t =(t_1,t_2,\cdots ,t_n)$ takie, że $t_1,t_2,\cdots ,t_n \in \{0, 1, 2\}$ .
Jest ich $3n$ . Dla każdego z nich niech $S_t$ oznacza sumę $t_1x_1 +t_2x_2 +\cdots +t_nx_n$ .
Ponieważ liczby $x_1,x_2,\cdots ,x_n$ są nieujemne i ich suma wynosi 1, więc zachodzą nierówności

$ 0=0 \cdot x_1 +0 \cdot x_2 + \cdots +0 \cdots x_n \leqslant S_t \leqslant 2 \cdot x_1 +2 \cdot x_2 + \cdots +2 \cdot x_n =2. $

Z zasady szufladkowej Dirichleta wynika, że istnieją dwa różne ciągi $b =(b_1,b_2,\cdots ,b_n)$
oraz $c = (c_1,c_2,\cdots ,c_n)$ o wyrazach w zbiorze $\{0, 1, 2\}$ takie, że odpowiadające im sumy
$S_{b}$ oraz $S_{c}$ należą do tego samego spośród $3n -1$ przedziałów
$[0, \frac{2}{3^n-1})$ , $[\frac{2}{3^n-1}, \frac{4}{3^n-1})$ , $[\frac{4}{3^n-1}, \frac{6}{3^n-1})$ ,
$\cdots, [\frac{2(3^n-5)}{3^n-1}, \frac{3^n-3}{3^n-1})$ , $[\frac{2(3^n-3)}{3^n-1}, 2]$ .
Bez zmniejszania ogólności rozumowania możemy założyć, że $S_{b}$ . $S_{c}$ i wówczas

$ (1) \qquad 0 \leqslant S_{c} - S_{b} \leqslant \frac{2}{3^n-1}. $

Pokażemy, że warunki zadania spełnia ciąg $a =(a_1,a_2,\cdots ,a_n)$ określony wzorem

$ a_i =2+ c_i - b_i \quad \text{ dla }i =1, 2, \cdots , n. $

Każdy z jego wyrazów jest liczbą ze zbioru $\{0, 1, 2, 3, 4\}$ . Ponadto $b\neq (2, 2,\cdots , 2)$ ,
gdyż ciągi $b$ i $c$ są różne. Zachodzi także równość