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:

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

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!)$ :