XXXVI OM - I - Zadanie 9

W urnie jest 1985 kartek z napisanymi liczbami 1,2,3,..., 1985, każda lczba na innej kartce. Losujemy bez zwracania 100 kartek. Znaleźć wartość oczekiwaną sumy liczb napisanych na wylosowanych kartkach.

Rozwiązanie

Losowanie $ 100 $ kartek z urny zawierającej $ 1985 $ kartek można interpretować jako wybieranie $ 100 $-elementowego podzbioru zbioru $ 1985 $-elementowego. Zamiast danych liczb $ 1985 $ i $ 100 $ weźmy dowolne liczby naturalne $ n $ i $ k $, $ n \geq k $. Dla dowolnego $ k $-elementowego zbioru $ X $ będącego podzbiorem zbioru $ Z = \{1,2,\ldots,n\} $ oznaczmy przez $ s(X) $ sumę liczb w zbiorze $ X $. Ponumerujmy wszystkie $ k $-elementowe podzbiory $ Z $ liczbami od $ 1 $ do $ ???????????????? = \binom{n}{k}: X_1, \ldots, X_N $. Wybieramy losowo jeden z tych zbiorów. Prawdopodobieństwo każdego wyboru jest takie samo, a więc równa się $ p = 1 /N $. Wartość oczekiwana sumy liczb w tym zbiorze równa się

\[<br />
E = p \cdot s(X_1)+ \ldots +p \cdot s(X_N).<br />
\]

Policzymy, w ilu zbiorach $ X_i $ występuje dowolnie ustalona liczba $ x \in Z $. Liczbie $ x $ towarzyszy w każdym z tych zbiorów $ k-1 $ liczb dowolnie wybranych ze zbioru $ Z-\{x\} $. Możliwości jest $ M = \binom{n-1}{k-1} $. Wobec tego każda
liczba $ x \in Z $ występuje w $ M $ zbiorach $ X_i $; tak więc w sumie $ s = s(X_1)<br />
+ \ldots+s(X_N) $ każdy składnik $ x \in Z $ pojawia się $ M $ razy. Stąd $ s = M(1 +  2+ \ldots+n) = Mn(n+1)/2 $ i szukana wartość oczekiwana wynosi

\[<br />
E = ps \frac{n(n+1)}{2} \cdot \frac{M}{N} = \frac{n(n+1)}{2} \cdot \frac{(n-1)!}{(k-1)!(n-k)!} \cdot \frac{k!(n-k)!}{n!} = \frac{(n+1)k}{2}.<br />
\]

W naszym zadaniu $ n = 1985 $, $ k = 100 $, zatem $ E = 99 300 $.

Komentarze

Dodaj nową odpowiedź