XLVII OM - I - Zadanie 11

Zawody matematyczne:

XLVII OM, 1995-1996

Etap:

W konkursie skoków narciarskich uczestniczy 65 zawodników. Startują oni kolejno, według ustalonego wcześniej porządku. Każdy wykonuje jeden skok. Przyjmujemy, że uzyskane wyniki są różne od zera oraz że każda kolejność końcowa jest jednakowo prawdopodobna. W każdym momencie konkursu liderem nazywamy zawodnika, który do tego momentu uzyskał najlepszy wynik. Oznaczmy przez $p$ prawdopodobieństwo tego, że w czasie całego konkursu dokładnie jeden raz nastąpiła zmiana lidera. Wykazać, że $p > \frac{1}{16}$ .

Rozwiązanie

Będziemy rozpatrywać analogiczne zagadnienie dla dowolnej liczby uczestniczących zawodników. Oznaczmy tę liczbę przez $n$ . Zadanie polega na wyznaczeniu prawdopodobieństwa zdarzenia:

$ A : \textrm{w czasie konkursu ma miejsce dokładnie jedna zmiana lidera.} $

Dla każdej liczby $k \in \{0,1, \ldots, n-1 \}$ określamy następujące zdarzenie:

$ B_k \textrm{: najlepszy wynik został uzyskany w } (k-1) \textrm{-ym skoku.} $

Zgodnie z założeniem każda kolejność końcowa jest jednakowo prawdopodobna; stąd wynika, że zdarzenia $B_0, B_1, \ldots, B_{n-1}$ są jednakowo prawdopodobne: $P(B_k) = 1/n$ dla $k = 0,1,\ldots,n-1$ .

Przypuśćmy, że zaszło zdarzenie $B_0$ - to znaczy, że pierwszy skoczek zostaje liderem i już do końca konkursu nie oddaje prowadzenia; zmiana lidera nie następuje. Wyklucza to zajścia zdarzenia $A$ ; prawdopodobieństwo zdarzenia $A$ przy warunku $B_0$ jest więc zerowe: $P(A|B_0) = 0$ .

Ustalmy teraz wartość $k \in \{1, \ldots, n-1\}$ i przypuśćmy, że zaszło zdarzenie $B_k$ . Wynik $(k+1)$ -go skoku, jako najlepszy w całym konkursie, z konieczności przynosi zmianę lidera, i to już ostatnią. Warunek konieczny i dostateczny, aby była to zmiana jedyna, można sformułować następująco:

$ W_k: \begin{array}{l} \textrm{w serii początkowych } k \textrm{ skoków (od pierwszego do } k \textrm{-tego)}\\ \textrm{najlepszy wynik pada już w pierwszym skoku.} \end{array} $

Niezależnie od tego, jakie wyniki zostały uzyskane w tej serii $k$ skoków, każde ich uporządkowanie (w obrębie tej serii) jest jednakowo prawdopodobne. Najlepszy może być w niej wynik pierwszego, drugiego, $\ldots$ , $k$ -tego skoku, z jednakowym prawdopodobieństwem, równym $1/k$ .

Takie jest, w szczególności, prawdopodobieństwo spełnienia warunku $W_k$ , który - jak pamiętamy - jest równoważny zajściu zdarzenia $A$ pod warunkiem zajścia zdarzenia $B_k$ . Liczba $1/k$ jest więc prawdopodobieństwem warunkowym: $P(A|B_k) = 1/k$ dla $k = 1, \ldots, n-1$ .

Na podstawie wzoru na prawdopodobieństwo całkowite obliczamy:

$ (1) \qquad \quad P(A)= \sum_{k=0}^{n-1} P(A|B_k) \cdot P(B_k) = 0 + \sum_{k=1}^{n-1} \frac{1}{k} \cdot \frac{1}{n} = \frac{1}{n} \sum_{k=1}^{n-1} \frac{1}{k}. $

Dla $n = 65$ dostajemy prawdopodobieństwo, o które chodzi w zadaniu:

$ p = \frac{1}{65} \left(1+\frac{1}{2}+\frac{1}{3}+\ldots+\frac{1}{64}\right). $

Sumę $1+\frac{1}{2}+\frac{1}{3}+\ldots+\frac{1}{64}$ szacujemy z dołu grupując jej wyrazy, jak następuje:

$ 1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4} + \left(\frac{1}{5}+\ldots+\frac{1}{8}\right)+ \left(\frac{1}{9}+\ldots+\frac{1}{16}\right) + \left(\frac{1}{17}+\ldots+\frac{1}{32}\right)+ \left(\frac{1}{33}+\ldots+\frac{1}{64}\right). $

W pierwszym nawiasie mamy cztery składniki, w drugim osiem, w trzecim szesnaście, w czwartym - trzydzieści dwa. W każdym nawiasie najmniejszy jest składnik ostatni, więc suma liczb w pierwszym, drugim, trzecim, czwartym nawiasie szacuje się z dołu odpowiednio przez liczby: $4 \cdot \frac{1}{8}, 8 \cdot \frac{1}{16}, 16 \cdot \frac{1}{32}, 32 \cdot \frac{1}{64}$ . Każda z nich równa się $\frac{1}{2}$ ; łączna suma liczb w tych czterech nawiasach przekracza $2$ . Stąd, ostatecznie,

$ p > \frac{1}{65}\left(1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+2\right) = \frac{1}{65} \cdot \frac{49}{12} = \frac{196}{195} \cdot \frac{1}{16} > \frac{1}{16}. $

(Sumę $1+\frac{1}{2}+ \ldots +\frac{1}{64}$ można oczywiście obliczyć z dowolną dokładnością; wartość prawdopodobieństwa $p$ wynosi $0,07298\ldots$ z dokładnością do pięciu cyfr znaczących: jest to troszkę więcej niż $\frac{1}{14}$ .)

Uwaga 3. W numerze $5/1996$ czasopisma Matematyka Maciej Radziejewski (członek Komitetu Okręgowego Olimpiady Matematycznej w Poznaniu) w interesującym artykule O rozwiązaniach zadań olimpijskich dzieli się wrażeniami ze sprawdzania zadań 2, 4, 10 i 11 z zawodów pierwszego stopnia XLVII O. M.; niektóre myśli z tych omówień zostały wykorzystane w niniejszym opracowaniu. We wspomnianym artykule są naszkicowane także i inne sposoby podejścia, są skomentowane sytuacje pojawiające się w rozwiązaniach (jest na przykład wspomniany dualizm, o którym mowa wyżej, w Uwadze 2) oraz są analizowane różne wątki z prac uczniowskich.