Problem other/agh/2025/1.1.tex

\section*{Zadanie 1.}

\subsection*{Treść zadania}

W filharmonii grupa $n$ dziewcząt i $m$ chłopców, gdzie $n\geq m$, zajmuje $m + n$
sąsiednich numerowanych miejsc w jednym rzędzie.
Na ile sposobów mogą to
zrobić, tak aby każdy chłopiec siedział między dziewczętami?

\subsection*{Rozwiązanie}

Każdy chłopiec ma mieć po lewej i po prawej stronie dziewczynę, stąd żaden chłopiec nie może siedzieć na skraju oraz żaden nie może siedzieć obok innego chłopca.
Zatem:

\begin{enumerate}
\item Najpierw ustawiamy wszystkie $n$ dziewcząt w rzędzie — można to zrobić na $n!$ sposobów.
\item Między kolejnymi dziewczętami jest dokładnie $n-1$ „przerw” (miejsc, w które można wstawić pojedynczego chłopca tak, by był między dziewczynami). Aby każdy chłopiec miał po obu stronach dziewczyny, musimy wybrać $m$ z tych $n-1$ przerw. Liczba wyborów to $\binom{n-1}{m}$.
\item Wybrane $m$ miejsc zajmują różni chłopcy, których można permutować na $m!$ sposobów.
\end{enumerate}

Stąd łączna liczba dopuszczalnych ustawień (dla dającej się wykonać sytuacji) wynosi
$$
n!\cdot\binom{n-1}{m}\cdot m!
$$

\textbf{Uwaga o wykonalności}: \emph{warunek opisany w zadaniu może być spełniony tylko wtedy, gdy $m\leq n-1$ (bo dostępnych „przerw” między dziewczynami jest $n-1$). Dla $m>n-1$ liczba sposobów jest równa $0$.}

\subsection*{Odpowiedź}

$$
\text{\#ustawień}=
\begin{cases}
n!\cdot\binom{n-1}{m}\cdot m! & \text{gdy }m\leq n-1\\
0 & \text{gdy }m>n-1
\end{cases}
$$