XLVI OM - III - Zadanie 5

Zawody matematyczne:

XLVI OM, 1994-1995

Etap:

III

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

Przekształcamy ten iloczyn, jak następuje:

$ q_j = \frac{l!}{(l-j)!} \cdot \frac{(n-j)!}{n!} = \frac{l!(n-l)!}{n!} \cdot \frac{(n-j)!}{(l-j)!(n-l)!}= $

$ ={{n}\choose{l}}^{-1} {{n-j}\choose{n-l}} = {{n}\choose{m}}^{-1} {{n-j}\choose{m}} $

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

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

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

$ \sum_{s=m}^n {{s}\choose{m}} = {{n+1}\choose{m+1}} $

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

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

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ść

$ (3) \qquad \quad \frac{n+1}{m+1}=k. $

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

$ \frac{n + 1}{k} - 1 \leq \frac{n}{k} < \frac{n+1}{k} $

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

$ m= \left[ \frac{n}{k} \right] = \frac{n+1}{k}-1, $

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