XXXV OM - II - Zadanie 4

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

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

$ \begin{split} 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 =\\ = 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 =\\ = 3^n \cdot n! \cdot 2^n \cdot n! \cdot n! = 6^n \cdot (n!)^3 \end{split} $

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

$ \frac{6^n \cdot (n!)^3}{(3n)!} $