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:

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

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

\[<br />
p_j = P(X=j)\quad \textrm{dla}\quad i = 1,2,\ldots,n.<br />
\]

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

\[<br />
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<br />
\]

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

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

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

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

\[<br />
m= \left[ \frac{n}{k} \right] \geq 1, \quad l = n-m \leq n-1<br />
\]

(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

\[<br />
(1) \qquad \quad E(X) = q_0+q_1 +q_2 + \ldots + q_l.<br />
\]

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

\[<br />
(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}).<br />
\]

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).

Przekształcamy ten iloczyn, jak następuje:

\[<br />
q_j = \frac{l!}{(l-j)!} \cdot \frac{(n-j)!}{n!} = \frac{l!(n-l)!}{n!} \cdot \frac{(n-j)!}{(l-j)!(n-l)!}=<br />
\]
\[<br />
={{n}\choose{l}}^{-1} {{n-j}\choose{n-l}} = {{n}\choose{m}}^{-1} {{n-j}\choose{m}}<br />
\]

(bo $ l + m = n $). Po podstawieniu tych wyrażeń równość (1) przybiera postać

\[<br />
E(X) = {{n}\choose{m}}^{-1} \sum_{j=0}^{n-m} {{n-j}\choose{m}} = {{n}\choose{m}}^{-1} \sum_{s=m}^n {{s}\choose{m}}<br />
\]

(zastosowaliśmy zmianę wskaźnika sumowania: $ s = n-j $). Ostatnia suma daje się zwinąć w znany sposób:

\[<br />
\sum_{s=m}^n {{s}\choose{m}} = {{n+1}\choose{m+1}}<br />
\]

(por. rozwiązanie zadania 11 z zawodów pierwszego stopnia tej olimpiady: wzór (2) oraz Uwaga na stronie 51). Stąd

\[<br />
E(X) = {{n}\choose{m}}^{-1} {{n+1}\choose{m+1}} = \frac{m!(n-m)!}{n!} \cdot \frac{(n+1)!}{(m+1)!(n-m)!} = \frac{n+1}{m+1}.<br />
\]

W zadaniu chodzi o ustalenie warunków na to, by wartość $ E(X) $ była równa dokładnie $ k $ - czyli na to, by zachodziła równość

\[<br />
(3) \qquad \quad \frac{n+1}{m+1}=k.<br />
\]

Jeśli związek (3) zachodzi, to oczywiście $ k $ jest dzielnikiem liczby $ n + 1 $. Na odwrót, jeśli $ n+1 $ dzieli się przez $ k $, wówczas z nierówności

\[<br />
\frac{n + 1}{k} - 1 \leq \frac{n}{k} < \frac{n+1}{k}<br />
\]

(której skrajne człony są liczbami całkowitymi) wnosimy, że

\[<br />
m= \left[ \frac{n}{k} \right] = \frac{n+1}{k}-1,<br />
\]

czyli zachodzi równość (3).

Mamy więc odpowiedź: szukanymi wartościami $ k $ są wszystkie dzielniki liczby $ n + 1 $ należące do zbioru $ \{1,2,\ldots,n\} $.

Komentarze

Dodaj nową odpowiedź