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.


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ę






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






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