XLVI OM - III - Zadanie 5

Niech $n$ i $k$ będą liczbami naturalnymi. Z urny, w której znajduje się 11 kartek ponumerowanych liczbami od 1 do $n$ , losujemy kartki kolejno po jednej, bez zwracania. Gdy pojawi się kartka o numerze podzielnym przez $k$ , przerywamy losowanie. Dla ustalonego $n$ wyznaczyć te liczby $k \leq n$ , dla których wartość oczekiwana liczby wylosowanych kartek jest równa dokładnie $k$ .

Rozwiązanie

Ustalmy liczbę naturalną $k \in \{1,2,\ldots,n\}$ . Weźmy pod uwagę następujące zdarzenia:

$ \begin{array}{cl} \mathcal{A}_j: & \textrm{liczba podzielna przez } k\ \textrm{pojawia się po raz pierwszy} \\ & \textrm{w } j\ \textrm{-tym losowaniu}\ (j=1,2,\ldots,n);\\ \mathcal{B}_j: & \textrm{liczba podzielna przez } k\ \textrm{nie pojawia się} \\ & \textrm{w żadnym spośród pierwszych} j\ \textrm{losowań}\ (j=0,1,2,\ldots,n). \end{array} $

Oznaczmy prawdopodobieństwa tych zdarzeń: $p_j = P(\mathcal{A}_j)$ , $q_j=P(\mathcal{B}_j$ ). Oczywiście $\mathcal{B}_0$ jest zdarzeniem pewnym. Zatem $q_0=1$ .

Zajście zdarzenia $\mathcal{A}_j$ jest równoważne temu, że wylosowano $j$ kartek, po czym losowanie przerwano - czyli temu, że rozważana w zadaniu zmienna losowa $X$ (liczba wylosowanych kartek) przyjmuje wartość $j$ . Tak więc

$ p_j = P(X=j)\quad \textrm{dla}\quad i = 1,2,\ldots,n. $

Zajście zdarzenia $\mathcal{A}_j$ jest jednocześnie równoważne temu, że liczba podzielna przez $k$ nie pojawiła się w pierwszych $j-1$ losowaniach, natomiast pojawiła się w pierwszych $j$ losowaniach - czyli że zaszło zdarzenie $\mathcal{B}_{j-1}$ , ale nie zaszło zdarzenie $\mathcal{B}_j$ . Inaczej mówiąc, zdarzenie $\mathcal{A}_j$ jest równe różnicy zdarzeń $\mathcal{B}_{j-1}$ i $\mathcal{B}_j$ (traktowanych jako podzbiory odpowiedniej przestrzeni probabilistycznej). Wobec tego

$ p_j = P(\mathcal{B}_{j-1} \setminus \mathcal{B}_j) = q_{j-1}-q_j \quad \textrm{dla}\quad j = 1,2,\ldots,n $

(korzystamy z tego, że $\mathcal{B}_j \subset \mathcal{B}_{j-1}$ ).

Wartość oczekiwana zmiennej losowej $X$ równa się

$ \begin{split} E(X) & = \sum_{j=1}^n j \cdot P(X=j) = \sum_{j=1}^n j \cdot p_j = \sum_{j=1}^n j(q_{j-1} - q_j)=\\ & = (q_0-q_1) + 2(q_1 -q_2) + 3(q_2 -q_3) + \ldots + n(q_{n-1} -q_n) = \\ & = q_0 + q_1 + q_2 + \ldots + q_{n-1} -nq_n. \end{split} $

W zbiorze $\{1,2,\ldots,n\}$ jest $m$ liczb podzielnych przez $k$ oraz jest $l$ liczb niepodzielnych przez $k$ , przy czym

$ m= \left[ \frac{n}{k} \right] \geq 1, \quad l = n-m \leq n-1 $

(symbol $[t]$ oznacza, jak zwykle, największą liczbę całkowitą, nie przekraczają $t$ ). Jeżeli $j > l$ , to w którymś z pierwszych $j$ losowań musiała pojawić się liczba podzielna przez $k$ , co oznacza, że $\mathcal{B}_j$ jest zdarzeniem niemożliwym. Zatem $q_j = 0$ dla $j > l$ , i w takim razie

$ (1) \qquad \quad E(X) = q_0+q_1 +q_2 + \ldots + q_l. $

Z warunków zadania wynika, że dla $j \leq l$ prawdopodobieństwa $q_j$ wyrażają się wzorem

$ (2) \qquad \quad q_j=P(\mathcal{B}_j) = \frac{l}{n} \cdot \frac{l-1}{n-1} \cdot \ldots \cdot \frac{l-j+1}{n-j+1} \quad (j\ \textrm{czynników}). $

Istotnie: w pierwszym losowaniu wyciągamy liczbę niepodzielną przez $k$ z prawdopodobieństwem $l/n$ ; zostaje w urnie $n-1$ kartek, w tym $l-1$ kartek z liczbami niepodzielnymi przez $k$ ; w drugim losowaniu wyciągamy liczbę niepodzielną przez $k$ z prawdopodobieństwem $(l- 1)/(n- 1)$ ; i tak dalej. Wyciągnięcie w $j$ kolejnych losowaniach kartek z liczbami niepodzielnymi przez $k$ odbywa się z prawdopodobieństwem równym iloczynowi napisanemu po prawej stronie wzoru (2).