XXV - I - Zadanie 11

Zawody matematyczne:

XXV OM, 1973-1974

Etap:

Niech $X_n$ i $Y_n$ bądą niezależnymi zmiennymi losowymi o tym samym rozkładzie $\left{ \left(\frac{k}{2^n}, \frac{1}{2^n}\right) : k = 0, 1, \ldots, 2^n-1\right}$ . Oznaczmy przez $p_n$ prawdopodobieństwo zdarzenia, że istnieje liczba rzeczywista $t$ spełniająca równanie $t^2 + X_n \cdot t + Y_n = 0$ . Obliczyć $\lim_{n\to\infty} p_n$ .

Rozwiązanie

Zdarzenie sprzyjające polega na tym, że wyróżnik trójmianu $t^2 + X_n t + Y_n$ jest liczbą nieujemną. Niech $\displaystyle X_n = \frac{r}{2^n}$ , $\displaystyle Y_n = \frac{s}{2^n}$ , gdzie $r, s = 0, 1, \ldots, 2^n - 1$ . Nierówność $X_n^2 - 4 Y_n \geq 0$ jest równoważna nierówności $r^2 - 4 \cdot 2^n s \geq 0$ , czyli

$ (1) \qquad 0 \leq s \leq \frac{r^2}{4 \cdot 2^n}. $

Znajdziemy więc liczbę takich par $(r, s)$ , dla których zachodzi (1). Dla dowolnego $a$ liczba rozwiązań nierówności $0 \leq x \leq a$ w liczbach całkowitych $x$ jest równa $[a] + 1$ , gdzie $[a]$ jest największą liczbą całkowitą nie przekraczającą $a$ . Zatem liczba par $(r, s)$ spełniających
(1) jest równa

$ A_n = \sum_{r=0}^{2^n-1} \left( \left[ \frac{r^2}{4 \cdot 2^n} \right] +1 \right). $

Rozważmy sumę

$ B_n = \sum_{r=0}^{2^n-1} \frac{r^2}{4 \cdot 2^n} = \frac{1}{4 \cdot 2^n} \sum_{r=0}^{2^n-1} r^2. $

Na mocy wzoru

$ 1^2 + 2^2 + \ldots + k^2 = \frac{1}{6} k(k+ 1)(2k+1) $

mamy

$ (2) \qquad B_n = \frac{1}{4 \cdot 2^n} \cdot \frac{1}{6}(2^n - 1) 2^n (2^{n+1} - 1) = \frac{1}{12} \left( 2^{2n} - 3 \cdot 2^{n-1} + \frac{1}{2} \right). $

Ponieważ dla dowolnej liczby rzeczywistej x zachodzi nierówność

$ x < [x] + 1 \leq x + 1, $

więc

$ (3) \qquad B_n < A_n \leq \sum_{r=0}^{2^n-1} \left( \frac{r^2}{4 \cdot 2^n} + 1 \right) = B_n + 2^n. $

Liczba wszystkich zdarzeń elementarnych, czyli rozważanych par $(r, s)$ , jest równa $2^{2n}$ . Wobec tego $\displaystyle p^n = \frac{A^n}{2^{2n}}$ i z (3) wynika, że

$ (4) \qquad \frac{B_n}{2^{2n}} < p_n \leq \frac{B_n}{2^{2n}} + \frac{1}{2^n}. $

Z (2) otrzymujemy, że $\displaystyle \lim_{n \to \infty} \frac{B_n}{2^{2n}} = \frac{1}{12}$ i wobec tego z (4) wnosimy, że $\displaystyle \lim_{n \to \infty} p_n = \frac{1}{12}$