XXXIV OM - II - Zadanie 6

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

om34_2r_img_10.jpg
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 $.

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

Komentarze

Dodaj nową odpowiedź