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