Komentarz

XL OM - I - Zadanie 8

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:

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

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

\[<br /> \lim_{n\to \infty} a_k^{(m)} = \frac{1}{n}(a_1^{(1)} + \ldots + a_n^{(1)})<br /> \]

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

Rozwiązanie

Przyjmijmy oznaczenia:

\[<br /> u^{(m)}=\min_{1\leq k \leq n} a_k^{(m)}, \quad v^{(m)}=\max_{1\leq k \leq n} a_k^{(m)},<br /> \]
\[<br /> s^{(m)}=\sum_{k=1}^n a_k^{(m)},\quad q^{(m)}=\sum_{k=1}^n\left(a_k^{(m)}\right)^2.<br /> \]

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

\[<br /> (1) \qquad \lim_{m \to \infty} u^{(m)} = \lim_{m \to \infty} v^{(m)} = \frac{s}{n} .<br /> \]

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

\[<br /> u^{(m)} \leq \frac{s^{(m)}}{n} \leq v^{(m)}<br /> \]

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

\[<br /> (2) \qquad u^{(m)} \leq \frac{s^{(m)}}{n} \leq v^{(m)}<br /> \]

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

\[<br /> u^{(m)} \leq u^{(m+1)}, \quad v^{(m)} \geq v^{(m+1)};<br /> \]

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

\[<br /> u = \lim u^{(m)}\leq \frac{s}{n} , \quad v = \lim v^{(m)}\leq \frac{s}{n}.<br /> \]

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

\[<br /> \begin{split}<br /> 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=\\<br /> &= \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=\\<br /> &=\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=\\<br /> &=\left(a_i^{(m)}+a_j^{(m)}\right)^2<br /> \end{split}<br /> \]

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

\[<br /> (3) \qquad q^{(m)}-q^{(m+1)} = \left(a_{i_m}^{(m)}+a_{j_m}^{(m)}\right)^2.<br /> \]

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:

\[<br /> d=\frac{v-u}{n-1}>0.<br /> \]

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

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

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

\[<br /> P' = \langle u^{(M)};\ \alpha \rangle\quad \textrm{oraz} \quad P" = \langle \beta;\ v^{(M)} \rangle,<br /> \]

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

\[<br /> K' = \{k: a_k^{(M)} \in P'\} ,<br /> \]
\[<br /> K'' = \{k : a_k^{(M)} \in P''\};<br /> \]

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

\[<br /> a_k^{(M+1)} \in P' \quad \textrm{dla } k \in K'<br /> \]
\[<br /> a_k^{(M+1)} \in P'' \quad \textrm{dla } k \in K''<br /> \]

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

\[<br /> \{i_m,j_m\} \subset K' \quad \textrm{lub} \quad \{i_m,j_m\} \subset K'' \quad \textrm{dla}\quad m\geq M.<br /> \]

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

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Dodaj komentarz