XXXV OM - II - Zadanie 4

W zawodach Olimpiady Matematycznej bierze udział $ 3n $ uczestników. Mają oni wyznaczone miejsca w trzech rzędach, po $ n $ miejsc w każdym i są wpuszczani na salę pojedynczo, po czym natychmiast zajmują swoje miejsca. Obliczyć prawdopodobieństwo tego, że aż do momentu zajęcia miejsca przez ostatniego zawodnika, w każdej chwili dla każdych dwóch rzędów różnica liczb siedzących w nich zawodników jest nie większa od 1.

Rozwiązanie

Zdarzeniami elementarnymi są permutacje zbioru $ 3n $-elementowego. Liczba ich wynosi $ (3n)! $. Obliczymy liczbę zdarzeń sprzyjających zdarzeniu wymienionemu w treści zadania. Jako pierwszy może wyjść na salę dowolny zawodnik (jest więc $ 3n $ możliwości). Następna osoba może być jedną z $ 2n $ tych, których miejsca nie są wyznaczone w rzędzie, w którym siedzi pierwszy zawodnik. Trzecim wchodzącym na salę uczestnikiem powinien być ktoś mający miejsce w rzędzie, w którym nie siedzi żaden z poprzednio wpuszczonych zawodników (jest $ n $ takich możliwości). Następną osobą może być ktokolwiek z pozostałych $ 3(n -1) $ osób. Kolejna osoba nie może usiąść w rzędzie, w którym siedzą już dwie osoby, jest więc $ 2(n- 1) $ możliwości wyboru tego zawodnika. Szósta osoba wpuszczana na salę powinna być jedną z $ n - 1 $ osób, których miejsce jest w rzędzie zajętym tylko przez jednego zawodnika. Następnie sytuacja znów się powtarza: we wszystkich rzędach siedzą po dwie osoby, przed wejściem czeka $ 3 (n - 2) $ zawodników. Teraz może wejść którykolwiek z nich, po nim ktoś z $ 2(n - 2) $ tych, których miejsca są w innych rzędach niż miejsce ostatnio wpuszczonego itd. Liczba zdarzeń sprzyjających wynosi więc

\[<br />
\begin{split}<br />
3n \cdot 2n \cdot n \cdot 3 (n - 1) \cdot 2 (n - 1) \cdot (n - 1) \cdot 3 (n - 2) \cdot 2 (n - 2) \cdot (n - 2) \ldots  3 \cdot 2 \cdot 1 =\\<br />
= 3n \cdot 3(n-1) \cdot 3(n-2) \cdot \ldots \cdot 3 \cdot 2n \cdot 2(n-1) \cdot 2(n-2) \cdot \ldots \cdot 2 \cdot n \cdot (n-1) \cdot (n-2) \cdot \ldots 1 =\\<br />
= 3^n \cdot n! \cdot 2^n \cdot n! \cdot n! = 6^n \cdot (n!)^3<br />
\end{split}<br />
\]

(Podany tu opis można oczywiście zastąpić dowodem indukcyjnym). Wobec tego szukane prawdopodobieństwo wynosi

\[<br />
\frac{6^n \cdot (n!)^3}{(3n)!}<br />
\]

Komentarze

Dodaj nową odpowiedź