LVI OM - I - Zadanie 10

Zawody matematyczne:

LVI OM, 2004-2005

Etap:

Spośród wszystkich podzbiorów ustalonego zbioru $n$ -elementowego $X$ losujemy kolejno ze zwracaniem trzy zbiory $A$ , $B$ , $C$ . Za każdym razem wylosowanie każdego spośród $2^n$ podzbiorów zbioru $X$ jest jednakowo prawdopodobne. Wyznaczyć najbardziej prawdopodobną liczbę elementów zbioru $A\cap B\cap C$ .

Rozwiązanie

Zbiór zdarzeń elementarnych $\Omega$ składa się ze wszystkich trójek $(A,B,C)$ , gdzie $A$ , $B$ i $C$ są podzbiorami danego zbioru $n$ -elementowego $S$ . Wylosowanie każdej z $(2^n)^3 =8^n$ trójek $(A,B,C)$ jest jednakowo prawdopodobne. Niech $X_k$ $(k =0,1,2,\ldots,n)$ oznacza zdarzenie polegające na tym, że trójka zbiorów $(A,B,C)$ spełnia warunek $|A\cap B\cap C|= k$ , gdzie $|F|$ oznacza liczbę elementów zbioru $F$ . Szukamy takiej liczby naturalnej $k$ , dla której prawdopodobieństwo zajścia zdarzenia $X_k$ jest największe.

Ustalmy liczbę $k\in\{0,1,2, \ldots,n\}$ . Obliczymy liczbę trójek $(A, B, C)$ , dla których $|A\cap B\cap C|=k$ .

Jeśli $(A,B,C)$ jest trójką podzbiorów zbioru $S$ , to każdy element zbioru $S$ znajduje się w dokładnie jednym spośród następujących ośmiu zbiorów

$ (1)\qquad \begin{array}{l} A\cap B\cap C,\ (A\cap B)\backslash C,\ (B\cap C)\backslash A,\ (C\cap A)\backslash B,\\ A\backslash (B\cup C),\ B\backslash (C\cup A),\ C\backslash (A\cup B),\ S\backslash (A\cup B\cup C). \end{array} $

Aby uzyskać trójkę zbiorów $(A,\ B,\ C)$ , dla których $|A\cap B\cap C|=k$ , wybieramy najpierw $k$ elementów zbioru $S$ , które umieścimy w zbiorze $A\cap B\cap C$ — możemy to uczynić na $n \choose k$ sposobów. Każdemu z pozostałych $n-k$ elementów $k$ przyporządkowujemy jedną z pozostałych siedmiu możliwości występujących w (1) — możemy to zrobić na $7^{n-k}$ sposobów. Opisane postępowanie określa jednoznacznie trójkę $(A,B,C)$ . Zatem liczba trójek $(A,B,C)$ , dla których $|A \cap B \cap C| = k$ wynosi ${n \choose k} \cdot 7^{n-k}$ . Stąd uzyskujemy

$ P(X_{k})=\frac{{n \choose k} \cdot 7^{n-k}}{8^{n}}. $

Aby wyznaczyć taką liczbę $k$ , dla której prawdopodobieństwo zajścia zdarzenia $X_k$ jest największe, obliczamy iloraz

$ \frac{P(X_{k+1})}{P(X_{k})}=\frac{n-k}{7k+7}. $

Stąd wynika, że

$ \left\{ \begin{array}{ll} P(X_{k+1})>P(X_k),&\textrm{jeśli}\ k<\frac{1}{8}(n-7);\\ P(X_{k+1})<P(X_k),&\textrm{jeśli}\ k>\frac{1}{8}(n-7);\\ P(X_{k+1})=P(X_k),&\textrm{jeśli}\ k=\frac{1}{8}(n-7).\\ \end{array}\right. $

Oznaczając $\lambda=[(n-7)/8]$ , gdzie $[x]$ jest największą liczbą całkowitą nie większą od $x$ , otrzymujemy

$ \begin{array}{l} P(X_{0})<P(X_{1})<P(X_{2})<\ldots<P(X_{\lambda})\leq P(X_{\lambda+1}),\\ P(X_{\lambda+1})>P(X_{\lambda+2})>\ldots>P(X_{n}). \end{array} $

Zatem prawdopodobieństwo $P (X_k)$ jest największe dla $k = \lambda+1 =[ \frac{1}{8} (n+1)]$ .

Jeśli $\frac{1}{8}(n-7)$ jest liczbą całkowitą, to istnieją dwie wartości $k$ , dla których liczba $P(X_k)$ jest największa, a mianowicie $k = \frac{1}{8} (n-7)$ oraz $k = \frac{1}{8} (n+1)$ .