XLI OM - I - Zadanie 11

W urnie znajduje się n kartek ponumerowanych liczbami od 1 do $ n $. Wyciągamy z urny bez zwracania kolejno $ k $ kartek; $ n $ i $ k $ są ustalonymi liczbami naturalnymi, $ 1 \leq k \leq n $. Niech $ x_i $ będzie numerem $ i $-tej wyciągniętej kartki. Obliczyć prawdopodobieństwo tego, że w ciągu $ (0,x_1,\ldots, x_k, 0) $ jest dokładnie jedno maksimum lokalne.

Uwaga. Wyraz ciągu nazywamy maksimum lokalnym, jeśli jest liczbą większą od obu wyrazów sąsiednich.

Rozwiązanie

Zajmiemy się najpierw przypadkiem szczególnym, w którym wyciągnięte kartki noszą numery od $ 1 $ do $ k $ (w pewnym porządku). Zakładamy więc, że zachodzi równość zbiorów $ \{ x_1, \ldots, x_k \} = \{ 1, /ldots, k \}  $. Kolejność pojawiania się tych kartek w opisanym doświadczeniu wyznacza permutację $ (x_1 ,\ldots,x_k) $ zbioru $ \{ 1, /ldots, k \} $.

Największą liczbą w tym zbiorze jest liczba $ k $. Jeśli w ciągu $ (0,x_1,\ldots,x_k,0) $ ma wystąpić dokładnie jedno maksimum lokalne, musi nim być właśnie liczba $ k $. Wyrazy wcześniejsze, tj. występujące w danej permutacji przed $ k $, muszą utworzyć ciąg rosnący; wyrazy późniejsze - ciąg malejący. (Oczywiście, gdy $ k = x_1 $, wówczas pierwszy z tych ciągów jest pusty; gdy zaś $ k = x_k $ - drugi jest pusty.)

Zatem ustalenie zbioru liczb poprzedzających w danej permutacji liczbę $ k $ w pełni identyfikuje permutację (mającą jedyne maksimum lokalne); kolejność, w jakiej te oraz pozostałe liczby muszą wystąpić jest już zdeterminowana przez warunek nieistnienia więcej niż jednego lokalnego maksimum.

Zbiór liczb poprzedzających $ k $ może być dowolnym podzbiorem zbioru $ \{1,\ldots,k-1\} $ (może być w szczególności zbiorem pustym lub zbiorem, którego dopełnienie jest puste).

Mamy więc wzajemnie jednoznaczną odpowiedniość między podzbiorami zbioru $ \{1,\ldots,k - 1\} $ a rozważanymi permutacjami. Liczba podzbiorów zbioru $ (k - 1) $-elementowego wynosi $ 2^{k-1} $, tyle samo jest też więc permutacji zbioru $ \{1,\ldots,k\} $, w których występuje dokładnie jedno maksimum lokalne.

Ponieważ zaś liczba wszystkich permutacji zbioru $ k $-elementowego równa się $ k! $, zatem prawdopodobieństwo wystąpienia dokładnie jednego maksimum lokalnego, przy założeniu równości $ \{x_1,\ldots,x_k\} = \{1,\ldots,k\} $, wynosi $ 2^{k-1}/(k!) $.

Zauważmy teraz, że to założenie w gruncie rzeczy nie ogranicza ogólności rozważań. Niech $ K $ będzie dowolnie ustalonym $ k $-elementowym podzbiorem zbioru $ \{1,\ldots,n\} $ i przypuśćmy, że właśnie $ K $ jest zbiorem numerów wylosowanych kartek. Kolejność wyciągania kartek wyznacza permutację zbioru $ K $. Liczba permutacji mających tylko jedno maksimum lokalne (którym z konieczności musi być największa liczba zbioru $ K $) wynosi $ 2^{k-1} $, tak samo, jak w przypadku zbioru $ K = \{1,\ldots,k\} $. Liczba wszystkich permutacji zbioru $ K $ wynosi $ k! $. Prawdopodobieństwo, że losowo wybrana permutacja zbioru $ K $ ma dokładnie jedno maksimum lokalne, równa się $ 2^{k-1}/(k!) $.

Ponieważ dla każdego zbioru K otrzymujemy ten sam wynik, zatem otrzymana we wszystkich przypadkach wartość $ 2^{k-1}/(k!) $ jest odpowiedzią na postawione w zadaniu pytanie. Ta konkluzja, intuicyjnie jasna, może być uzasadniona w sposób bardziej formalny:

Niech $ K_1,\ldots,K_m $ będzie ciągiem wszystkich $ k $-elementowych podzbiorów zbioru $ \{1,\ldots,n\} $; kolejność ich numeracji jest bez znaczenia. (Oczywiście $ m = \binom{n}{k} $.) Ze zbioru $ \{1,\ldots,n\} $ wybieramy kolejno bez powtórzeń $ k $ elementów $ x_1,\ldots,x_k $. Rozważamy zdarzenia:

\[<br />
\begin{split}<br />
& A \colon \textrm{w ciągu} \ (0,x_1,\ldots,x_k,0)\ \textrm{jest dokładnie jedno maksimum lokalne};\\<br />
& B_1 \colon \textrm{zbiór} \ \{ x_1, \ldots, x_k \}\ \textrm{jest identyczny ze zbiorem } K_1;\\<br />
& B_2\colon \textrm{zbiór} \ \{ x_1, \ldots, x_k \}\ \textrm{jest identyczny ze zbiorem } K_2;\\<br />
& \hdots \\<br />
& B_m \colon \textrm{zbiór} \ \{ x_1, \ldots, x_k \}\ \textrm{jest identyczny ze zbiorem } K_m.<br />
\end{split}<br />
\]

Na mocy poprzednich rozważań, prawdopodobieństwo warunkowe zdarzenia $ A $, pod warunkiem zajścia zdarzenia $ B_i $, jest dla każdego $ i $ takie samo i równa się $ 2^{k-1} /(k!) $:

\[<br />
P(A|B_i) = \frac{2^{k-1}}{k!} \quad \textrm{dla} \ i=1,\ldots,m.<br />
\]

Zdarzenia $ B_i $ wyczerpują wszystkie możliwości i wzajemnie się wykluczają, a więc $ P(B_1) +\ldots+P(B_m) = 1 $.

Zgodnie z wzorem na prawdopodobieństwo całkowite:

\[<br />
P(A) = \sum_{i=1}^m P(A|B_i)P(B_i) = \frac{2^{k-1}}{k!} \sum_{i=1}^m P(B_i) = \frac{2^{k-1}}{k!}<br />
\]

Jest to szukana wartość.

Komentarze

Dodaj nową odpowiedź