XXXIV OM - II - Zadanie 6

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

Dla danej liczby $n$ oznaczmy przez $p_n$ prawdopodobieństwo tego, że przy losowym wyborze pary liczb całkowitych $k, m$ spełniających warunki $0 \leq k \leq m \leq 2^n$ (wybór każdej pary jest jednakowo prawdopodobny) liczba $\binom{m}{k}$ będzie parzysta. Obliczyć $\lim_{n\to \infty} p_n$ .

Rozwiązanie

Diagram na rysunku 10 przedstawia trójkąt Pascala napisany modulo $2$ , to znaczy mający zera i jedynki odpowiednio w tych miejscach, gdzie w zwykłym trójkącie Pascala występują liczby parzyste i nieparzyste. Jak w zwykłym trójkącie Pascala, tak i tu każdy element jest sumą elementów stojących bezpośrednio nad nim zgodnie z tabliczką dodawania modulo 2: $0+0=0$ , $0+1=1$ , $1+0=1$ , $1+1 = 0$ . Narysowane linie poziome dzielą ten trójkąt na warstwy:

warstwa $W_0$ złożona z wiersza nr $0$ ,
warstwa $W_1$ złożona z wiersza nr $1$ ,
warstwa $W_2$ złożona z wierszy nr $2$ i $3$ ,
warstwa $W_3$ złożona z wierszy nr $4$ , $5$ , $6$ , $7$ ,
$\ldots$
warstwa $W_j$ złożona z wierszy o numerach od $2^{j-1}$ do $2^j- 1$
$\ldots$

Udowodnimy indukcyjnie, że w dowolnej warstwie $W_j$ znajdują się dwa rozłączne trójkąty, z których każdy jest identyczny z trójkątem utworzonym przez warstwy $W_0, W_1, \ldots, W_{j-1}$ , oraz, że te dwa trójkąty są rozdzielone odwróconym trójkątem złożonym z samych zer; górny wiersz warstwy składa się ze skrajnych jedynek i samych zer, dolny zaś wiersz warstwy składa się z samych jedynek.

Dla $j= 1, 2, 3$ jest to widoczne z rysunków (linie ukośne wyznaczają podział na trójkąty, o których mowa). Załóżmy prawdziwość powyższych zależności dla pewnego $j$ i weźmy pod uwagę warstwę $W_{j + 1}$ .Z założenia indukcyjnego, ostatni wiersz warstwy $W_j$ ma postać $111\ldots 111$ , a zatem zgodnie z podaną wyżej regułą dodawania, pierwszy wiersz warstwy $W_{j + 1}$ ma postać $100\ldots 001$ . Skrajne jedynki tego wiersza dają początek dwóm nowym kopiom trójkąta Pascala, a pomiędzy nimi znajdują się zera. Warstwa $W_{j + 1}$ ma tyle samo wierszy, co warstwy $W_0, W_1, \ldots, W_j$ razem wzięte, więc w podstawie każdego z tych dwóch trójkątów na dole warstwy $W_{j + 1}$ znajdzie się ten sam układ cyfr, co i w ostatnim wierszu warstwy $W_j$ , czyli rząd jedynek. Wypełnią one ostatni rząd warstwy $W_{j + 1}$ . Kończy to dowód tezy indukcyjnej.

Liczba $p_n$ określona w zadaniu równa się stosunkowi liczby zer w wierszach o numerach od $0$ do $2^n$ do liczby wszystkich elementów tych wierszy. Wiersze te obejmują warstwy $W_0, W_1, \ldots, W_n$ oraz pierwszy wiersz warstwy $W_{n+1}$ . Z wyżej udowodnionego związku wynika, że w sumie warstw $W_0, \ldots, W_j$ jest trzykrotnie więcej jedynek, niż w sumie warstw $W_0, \ldots, W_{j-1}\ (j = 1, 2, 3,\ldots)$ , a ponieważ w warstwie $W_0$ jest jedna jedynka, więc w sumie warstw $W_0, \ldots, W_n$ jest $3^n$ jedynek. Doliczając do tego dwie skrajne jedynki następnego wiersza widzimy, że w rozważanym fragmencie trójkąta Pascala jest $a_n = 3^n+ 2$ jedynek. Wszystkich elementów jest w tym fragmencie $b_n= 1 + 2 + 3 + \ldots+ (2^n+ 1) = (2^n+ 1) (2^n+ 2) /2$ , a więc jest tam $b_n- a_n$ zer. Badane prawdopodobieństwo równa się

$<br /> p_n = \frac{b_n-a_n}{b_n} = 1 - \frac{a_n}{b_n} = 1 - \frac{2(3^n+2)}{4^n+3 \cdot 2^n + 2} =<br /> 1 - \frac{2 \left( \left( \frac{3}{4}\right)^n + 2\left( \frac{1}{4} \right)^n \right)}{1 + 3 \left( \frac{2}{4}\right)^n + 2 \left( \frac{1}{4}^n \right)}.<br />$

Stąd $\displaystyle \lim_{n \to \infty} p_n = 1$ .