XXXVI OM - I - Zadanie 9

Zawody matematyczne:

XXXVI OM, 1984-1985

Etap:

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ę

$ E = p \cdot s(X_1)+ \ldots +p \cdot s(X_N). $

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) + \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