|
|
 |
Условие
К Ивану на день рождения пришли 3 n гостей.
У Ивана есть 3 n цилиндров с написанными сверху буквами А, Б и В, по n штук каждого типа.
Иван хочет устроить бал: надеть на гостей цилиндры и выстроить их в хороводы (один или больше) так,
чтобы длина каждого хоровода делилась на 3, а при взгляде на любой хоровод сверху читалось бы по часовой стрелке АБВАБВ...АБВ.
Докажите, что Иван может устроить бал ровно (3n)! различными способами. (Цилиндры с одинаковыми буквами неразличимы; все гости различны.)
Решение
Первое решение. Разобьём всех гостей на упорядоченные тройки; первому человеку из тройки наденем цилиндр с буквой А, второму — с буквой Б, третьему — с буквой В. Для этого поставим гостей в шеренгу (это можно сделать (3n)! способами), первых трёх объединим в одну тройку, вторых трёх — в другую и т.д. Поскольку тройки можно переставлять внутри шеренги и получать то же самое разбиение на тройки, то каждое разбиение посчитано n! раз. Таким образом, количество способов разбить гостей на упорядоченные тройки равно (3n)! / n!.
Теперь для того, чтобы разбить гостей на хороводы, достаточно разбить на хороводы первых n человек из своих троек (эти хороводы могут состоять из одного человека), а затем поставить после каждого человека его тройку, что можно сделать единственным образом. Докажем индукцией по n, что количество способов сделать это равно n!, что завершит решение.
База для n = 1 очевидна. Пусть утверждение верно для n, докажем его для n + 1. Расставим n человек в хороводы, это можно сделать n! способами. В каждом разбиении на хороводы n человек есть ровно n + 1 место, куда можно поставить оставшегося человека: в каждом существующем хороводе из k человек таких мест ровно k, а ещё можно выделить этого человека в новый хоровод.
Замечание. Последнее рассуждение можно упростить, если заметить, что каждое разбиение на хороводы соответствует перестановке на множестве из n элементов, представленной в форме циклов, а количество перестановок, как известно, равно n!.
Второе решение. Занумеруем людей числами от 1 до 3n. Есть как раз (3n)! способов расставить этих людей в ряд, поэтому достаточно установить взаимно однозначное соответствие между такими расстановками и разбиениями на хороводы.
Возьмём любую расстановку, наденем всем цилиндры в порядке АБВАБВ...АБВ слева направо. Мысленно разделим людей подряд на n троек. В первый хоровод берём подряд всех людей от начала и до той тройки включительно, где стоит человек с номером 1 (и замыкаем в хоровод); во второй хоровод берём следующие тройки подряд до той включительно, где стоит человек с наименьшим из оставшихся номеров (и замыкаем в хоровод), и так далее.
Обратно, по набору хороводов легко восстановить расстановку: берём хоровод, где стоит человек 1, находим тройку AБВ, в которой он находится, «разрезаем» хоровод сразу за этой тройкой, вытягиваем в линию и ставим в начало расстановки. Далее берём человека с наименьшим номером из оставшихся, находим «его» хоровод, так же разрезаем и подсоединяем к расстановке и т.д.
