Komentarz

XLIII OM - I - Zadanie 11

Dana jest liczba naturalna $ n\geq 1 $. Rozważamy tabelę zbudowaną z $ n(n+1)/2 $ okienek, ustawionych w $ n $ rzędach: jedno okienko w pierwszym rzędzie, dwa w drugim itd., $ n $ okienek w $ n $-tym rzędzie. W okienka tabeli wpisujemy w sposób losowy liczby od $ 1 $ do $ n(n + l )/2 $. Niech $ m_k $ będzie największą z liczb w $ k $-tym rzędzie. Obliczyć prawdopodobieństwo tego, że $ m_1 < m_2 < \ldots < m_n $.

Rozwiązanie

Dla ustalonej liczby naturalnej $ n \geq 2 $ rozważane w zadaniu zdarzenie

\[<br /> \mathcal{A}_n \colon \textrm{zachodzą nierówności}\ m_1 < \ldots < m_n<br /> \]

jest równoważne koniunkcji zdarzeń

\[<br /> \mathcal{B}_n \colon \textrm{zachodzi nierówność}\ m_n > \max\{m_1, \ldots, m_{n-1} \}<br /> \]

oraz

\[<br /> \mathcal{C}_n \colon \textrm{zachodzą nierówności}\ m_1 < \ldots < m_{n-1}.<br /> \]

Warunek określający zdarzenie $ \mathcal{B}_n $ jest równoważny stwierdzeniu, że liczba $ N = n(n+ 1)/2 $ trafia do jednego z $ n $ okienek $ n $-tego rzędu tabeli; w takim razie

\[<br /> P(\mathcal{B}_n) = \frac{n}{N}=\frac{2}{n+1}.<br /> \]

Wybierzmy dowolne $ n $ liczb ze zbioru $ \{1,2,\ldots,N\} $ i przyjmijmy, że te liczby zostały wpisane w okienka $ n $-tego rzędu. Pozostaje zbiór $ M $ różnych liczb, gdzie $ M = N - n= n(n - 1 )/2 $; należy je rozmieścić w okienkach od pierwszego do ($ n - 1 $)-go rzędu.

Zbiór ten możemy zastąpić po prostu zbiorem $ \{1,2,\ldots,M\} $; prawdopodobieństwo zajścia nierówności $ m_1 \leq \ldots \leq m_{n} $ nie zmieni się przy tym.

Uwaga ta jest słuszna dla każdego wyboru $ n $ liczb (do $ n $-tego rzędu tabeli); w szczególności dla każdego takiego wyboru, który powoduje zajście zdarzenia $ \mathcal{B}_n $. Wobec tego prawdopodobieństwo warunkowe $ P(\mathcal{C}_n \mid \mathcal{B}_n) $ jest równe prawdopodobieństwu zdarzenia $ \mathcal{A}_{n-1} $ i otrzymujemy wzór rekurencyjny

\[<br /> P(\mathcal{A}_n) = P(\mathcal{B}_n \cap \mathcal{C}_n) = P(\mathcal{C}_n \mid \mathcal{B}_n) \cdot P(\mathcal{B}_n) = P(\mathcal{A}_{n-1}) \cdot \frac{2}{n+1}.<br /> \]

Ponieważ $ P(\mathcal{A}_1) = 1 $, zatem

\[<br /> P(\mathcal{A}_n) = \frac{2}{3} \cdot \frac{2}{4} \cdot \ldots \frac{2}{n+1} =\frac{2^n}{(n+1)!}.<br /> \]
  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Dodaj komentarz