|
|
 |
Условие
К Ивану на день рождения пришли 2$N$ гостей. У Ивана есть $N$ чёрных и $N$ белых цилиндров. Он хочет устроить бал: надеть на гостей цилиндры и выстроить их в хороводы (один или несколько) так, чтобы в каждом хороводе было хотя бы два человека и люди в цилиндрах одного цвета не стояли в хороводе рядом. Докажите, что Иван может устроить бал ровно $(2N)!$ различными способами. (Цилиндры одного цвета неразличимы; все гости различимы.)
Решение 1
Занумеруем людей числами от 1 до 2$N$. Есть как раз $(2N)!$ способов расставить этих людей в ряд, поэтому достаточно установить взаимно-однозначное соответствие между такими расстановками и разбиениями на хороводы.
Возьмём любую расстановку, наденем всем цилиндры в порядке ЧБЧБ...ЧБ слева-направо. Мысленно разделим людей на пары соседних. В первый хоровод берём подряд всех людей от начала и до той пары включительно, где стоит человек 1 (и замыкаем в хоровод); во второй хоровод берём следующие пары подряд до той включительно, где стоит человек с наименьшим из оставшихся номеров (и замыкаем в хоровод), и т.д.
Обратно, по набору хороводов легко восстановить расстановку: берём хоровод, где стоит человек 1, находим пару ЧБ, в которой он находится, "разрезаем" хоровод сразу за этой парой, вытягиваем в линию и ставим в начало расстановки.
Далее берём человека с наименьшим номером из оставшихся, так же разрезаем хоровод за его парой и подсоединяем к расстановке, и т.д.
Решение 2
"Белых" гостей можно выбрать $C_{2N}^N$ способами. Для каждого из них разбить "белых" гостей на циклы (длины от 1 до $N$) можно $N!$ способами (так как каждая перестановка однозначно разбивается в произведение независимых циклов). Для каждого из них вставить между "белыми" гостями "чёрных" можно $N!$ способами. В итоге получаем $C_{2N}^N\cdot N! \cdot N! = (2N)!$ различных балов. Ясно, что все балы рассмотрены.
Замечания
9 баллов
