XL OM - I - Zadanie 8

Zawody matematyczne:

XL OM, 1988-1989

Etap:

Dana jest liczba naturalna $n$ oraz skończony ciąg liczb rzeczywistych $A^{(1)}= (a_1^{(1)}, a_2^{(1)}, \ldots, a_n^{(1)})$ . Dla każdej liczby naturalnej $m$ wybieramy dwie liczby naturalne $i$ , $j$ spełniające warunek $1 \leq i < j \leq n$ i określamy ciąg $A^{(m+1)}= (a_1^{(m+1)}, a_2^{(m+1)}, \ldots, a_n^{(m+1)})$ , jak następuje:

$ \begin{split} a_i^{(m+1)} &= a_j^{(m+1)} = \frac{1}{2}(a_i^{(m)} + a_j^{(m)}),\\ a_k^{(m+1)} = a_k^{(m)} \quad\text{dla}\quad k\neq i, j. \end{split} $

Udowodnić, że jeżeli każda para liczb naturalnych $(i,j)$ należących do przedziału $\langle 1;n\rangle$ będzie wybrana nieskończenie wiele razy, to

$ \lim_{n\to \infty} a_k^{(m)} = \frac{1}{n}(a_1^{(1)} + \ldots + a_n^{(1)}) $

dla $k = 1,2,\ldots, n$ .

Rozwiązanie

Przyjmijmy oznaczenia:

$ u^{(m)}=\min_{1\leq k \leq n} a_k^{(m)}, \quad v^{(m)}=\max_{1\leq k \leq n} a_k^{(m)}, $

$ s^{(m)}=\sum_{k=1}^n a_k^{(m)},\quad q^{(m)}=\sum_{k=1}^n\left(a_k^{(m)}\right)^2. $

Sumę $s^{(1)}$ oznaczmy krótko przez $s$ . Teza zadania orzeka, że ciąg $\left(a_1^{(m)}\right)^\infty_{m=1}$ jest zbieżny do liczby $s/n$ , także ciąg $\left(a_2^{(m)}\right)^\infty_{m=1}$ Jest zbieżny do tej samej liczby, to samo można powiedzieć o ciągu $\left(a_3^{(m)}\right)^\infty_{m=1}$ , i tak dalej: dla każdego numeru $k \in \{1,\ldots, n\}$ ciąg $\left(a_k^{(m)}\right)^\infty_{m=1}$ jest zbieżny, a liczba $s/n$ jest wspólną granicą tych n ciągów. Sprowadza się to do wykazania, że

$ (1) \qquad \lim_{m \to \infty} u^{(m)} = \lim_{m \to \infty} v^{(m)} = \frac{s}{n} . $

Dla każdego $m$ zachodzą nierówności

$ u^{(m)} \leq \frac{s^{(m)}}{n} \leq v^{(m)} $

(średnia arytmetyczna układu liczb zawiera się między najmniejszą a największą z tych liczb). Zauważmy dalej, że opisana w zadaniu operacja nie zmienia sumy liczb: $s^{(m)} = s^{(m+1)}$ dla każdego $m$ ; a wobec tego $s^{(m)} = s$ dla wszystkich $m$ . Tak więc

$ (2) \qquad u^{(m)} \leq \frac{s^{(m)}}{n} \leq v^{(m)} $

Oczywiście $\rangle u^{(m)}, v^{(m)} \langle$ jest najmniejszym przedziałem zawierającym wszystkie liczby układu $A^{(m)}$ . Rozważana operacja nie wyprowadza poza ten przedział; układ $A^{(m+1)}$ także jest w nim zawarty. To znaczy, że

$ u^{(m)} \leq u^{(m+1)}, \quad v^{(m)} \geq v^{(m+1)}; $

ciąg $\left(u^{(m)}\right)$ jest niemalejący, a ciąg $\left(u^{(m)}\right)$ jest nierosnący. Nierówności (2) pokazują, że pierwszy z tych ciągów jest. ograniczony z góry przez liczbę $s/n$ , a drugi jest ograniczony z dołu przez tę samą liczbę. Istnieją zatem granice

$ u = \lim u^{(m)}\leq \frac{s}{n} , \quad v = \lim v^{(m)}\leq \frac{s}{n}. $

Jeśli wykażemy, że granice te są równe, to liczba $s/n$ będzie musiała być ich wspólną wartością i otrzymamy dowodzoną równość (1).

Przypuśćmy wobec tego, że $u < v$ . Mamy równość

$ \begin{split} q^{(m)}-q^{(m+1)}&= \sum_{k=1}^n \left(a_k^{(m)}\right)^2 - \sum_{k=1}^n \left(a_k^{(m+1)}\right)^2=\\ &= \left(a_i^{(m)}\right)^2 + \left(a_j^{(m)}\right)^2 - \left(a_i^{(m+1)}\right)^2 - \left(a_j^{(m+1)}\right)^2=\\ &=\left(a_i^{(m)}\right)^2+\left(a_j^{(m)}\right)^2 - 2\left(\frac{1}{2} \left(a_i^{(m)}+a_j^{(m)}\right)\right)^2=\\ &=\left(a_i^{(m)}+a_j^{(m)}\right)^2 \end{split} $

gdzie $(i,\ j)$ jest parą wskaźników wybraną w $m$ -tym kroku opisanej w zadaniu procedury (tj. przy określaniu układu liczb $A^{(m+1)}$ ). Ponieważ para ta zależy od bieżącej wartości wskaźnika $m$ , bardziej poprawnie będzie oznaczyć ją przez $(i_m,\ j_m)$ . Przepiszmy więc otrzymaną równość:

$ (3) \qquad q^{(m)}-q^{(m+1)} = \left(a_{i_m}^{(m)}+a_{j_m}^{(m)}\right)^2. $

Widać stąd, że $\left(q^{(m)}\right)$ jest nierosnącym ciągiem liczb nieujemnych, więc zbieżnym do granicy skończonej. Możemy wobec tego przejść do granicy z wyrażeniem znajdującym się po lewej stronie równości (3): ta różnica dąży do zera. Wobec tego także różnica w nawiasie po prawej stronie równości (3) musi dążyć do zera.

Założyliśmy, że $u < v$ . Oznaczmy liczbę $(v - u)/(n - 1)$ przez $d$ jest to ustalona liczba dodatnia:

$ d=\frac{v-u}{n-1}>0. $

Wyrazy ciągu zbieżnego do zera stają się od pewnego miejsca mniejsze od d. Istnieje więc taki numer $M$ , że

$ (4) \qquad \left| a_{i_m}^{(m)} - a_{j_m}^{(m)}) \right| < d \quad \textrm{dla } m\geq M. $

Weźmy pod uwagę przedział $\langle u^{(M)};\ v^{(M)} \rangle$ . Zawiera on przedział $\langle u;\ v \rangle$ , a więc ma długość nie mniejszą niż $v - u = (n - 1)d$ . Liczby $a_1^{(M)},\ldots, a_n^{(M)}$ dzielą ten przedział $n-1$ podprzedziałów (lub mniej, gdy niektóre z nich są równe). W każdym razie co najmniej jeden z tych podprzedziałów musi mieć długość nie mniejszą od $d$ . Ustalmy ten podprzedział i nazwijmy go $\langle \alpha;\ \beta \rangle$ .

Cały zbiór $\{a_1^{(M)},\ldots, a_n^{(M)}\}$ zawiera się w sumie przedziałów

$ P' = \langle u^{(M)};\ \alpha \rangle\quad \textrm{oraz} \quad P" = \langle \beta;\ v^{(M)} \rangle, $

odległych od siebie co najmniej o $d$ , przy czym w obu tych przedziałach są jakieś elementy tego zbioru. Przyjmijmy:

$ K' = \{k: a_k^{(M)} \in P'\} , $

$ K'' = \{k : a_k^{(M)} \in P''\}; $

są to niepuste zbiory wskaźników, dające w sumie zbiór $\{1,\ldots, n\}$ . Na mocy nierówności (4) (która musi zachodzić w szczególności dla $m = M$ ) wskaźniki $i_M$ , $j_M$ muszą oba należeć albo do $K'$ , albo do $K''$ . „Uśredniane" w $M$ -tym kroku liczby $a_{i_M}^{(M)}$ , $a_{j_M}^{(M)}$ obie leżą albo w przedziale $P'$ , albo w $P''$ . Ich średnia arytmetyczna także leży w tym przedziale. Tak więc

$ a_k^{(M+1)} \in P' \quad \textrm{dla } k \in K' $

$ a_k^{(M+1)} \in P'' \quad \textrm{dla } k \in K'' $

I znów, na mocy (4), wskaźniki $i_{M+1}$ i $j_{M+1}$ muszą oba należeć albo do $K'$ , albo do $K''$ . Kontynuując to rozumowanie dowodzimy indukcyjnie, że

$ \{i_m,j_m\} \subset K' \quad \textrm{lub} \quad \{i_m,j_m\} \subset K'' \quad \textrm{dla}\quad m\geq M. $

(Intuicyjny sens rozumowania jest taki: podprzedział $\langle \alpha;\ \beta \rangle$ stanowi ,,cezurę'' rozdzielającą całe ,,pole operacyjne'' na część lewą i prawą, których odległość wynosi nie mniej niż $d$ ; tymczasem nierówność (4) orzeka, że - począwszy od chwili $M$ - do ,,uśredniania'' wybiera się już tylko pary liczb odległych od siebie o mniej niż $d$ , a więc pary, których oba elementy leżą bądź w lewej, bądź w prawej części.)

Jeśli więc $(i,j)$ jest taką parą wskaźników, że $i\in K'$ , $j\in K''$ (lub odwrotnie), to $(i,j)\neq (i_m,j_m)$ dla wszystkich $m \geq M$ - wbrew warunkowi zadania mówiącemu, że każda para wskaźników pojawia się w ciągu wybranych par $(i_m,j_m)$ nieskończenie wiele razy.

Uzyskana sprzeczność pokazuje niesłuszność przypuszczenia, że $u < v$ , i tym samym kończy cały dowód.

Uwaga. Przypuśćmy, że $(i,j)$ jest parą wskaźników, która w ciągu wybranych par $(i_m,j_m)$ pojawia się nieskończenie wiele razy. Będziemy wówczas mówili, że wskaźniki $i$ oraz $j$ są stowarzyszone. Założenie zadania można wyrazić następująco: każde dwa wskaźniki $i,j \in \{1,\ldots,n\}$ są stowarzyszone. Zauważmy wszelako, że tak silne założenie nie jest nam potrzebne w dowodzie; wystarczy zakładać, że zbioru $\{1,\ldots ,n\}$ nie da się podzielić na dwa niepuste rozłączne podzbiory $K'$ i $K''$ tak, by żaden element zbioru $K'$ nie był stowarzyszony z żadnym elementem zbioru $K''$ ; udowodniona teza pozostaje w mocy, a dowód przenosi się bez żadnych zmian.