XLIII OM - I - Zadanie 11

Zawody matematyczne:

XLIII OM, 1991-1992

Etap:

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

$ \mathcal{A}_n \colon \textrm{zachodzą nierówności}\ m_1 < \ldots < m_n $

jest równoważne koniunkcji zdarzeń

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

oraz

$ \mathcal{C}_n \colon \textrm{zachodzą nierówności}\ m_1 < \ldots < m_{n-1}. $

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

$ P(\mathcal{B}_n) = \frac{n}{N}=\frac{2}{n+1}. $

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

$ 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}. $

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

$ P(\mathcal{A}_n) = \frac{2}{3} \cdot \frac{2}{4} \cdot \ldots \frac{2}{n+1} =\frac{2^n}{(n+1)!}. $