МОШ 2020, 9 класс, задача 5
К Ивану на день рождения пришли гостей. У Ивана есть цилиндров с написанными сверху буквами , и , по штук каждого типа. Иван хочет устроить бал: надеть на гостей цилиндры и выстроить их в хороводы (один или больше) так, чтобы длина каждого хоровода делилась на , и при взгляде на любой хоровод сверху читалось бы по часовой стрелке . Докажите, что Иван может устроить бал ровно различными способами. (Цилиндры с одинаковыми буквами неразличимы; все гости различны.)
Ответ
Первое решение. Разобьём всех гостей на упорядоченные тройки; первому человеку из тройки наденем цилиндр с буквой , второму — с буквой , третьему — с буквой . Для этого поставим гостей в шеренгу (это можно сделать способами), первых трёх объединим в одну тройку, вторых трёх — в другую и т. д. Поскольку тройки можно переставлять внутри шеренги и получать то же самое разбиение на тройки, то каждое разбиение посчитано раз. Таким образом, количество способов разбить гостей на упорядоченные тройки равно .
Теперь для того, чтобы разбить гостей на хороводы, достаточно разбить на хороводы первых человек из своих троек (эти хороводы могут состоять из одного человека), а затем поставить после каждого человека его тройку, что можно сделать единственным образом. Докажем индукцией по , что количество способов сделать это равно , что завершит решение.
База для очевидна. Пусть утверждение верно для , докажем его для . Расставим человек в хороводы, это можно сделать способами. В каждом разбиении на хороводы человек есть ровно место, куда можно поставить оставшегося человека: в каждом существующем хороводе из человек таких мест ровно , а ещё можно выделить этого человека в новый хоровод.
Замечание. Последнее рассуждение можно упростить, если заметить, что каждое разбиение на хороводы соответствует перестановке на множестве из элементов, представленной в форме циклов, а количество перестановок, как известно, равно .
Второе решение. Занумеруем людей числами от до . Есть как раз способов расставить этих людей в ряд, поэтому достаточно установить взаимно однозначное соответствие между такими расстановками и разбиениями на хороводы.
Возьмём любую расстановку, наденем всем цилиндры в порядке слева направо. Мысленно разделим людей подряд на троек. В первый хоровод берём подряд всех людей от начала и до той тройки включительно, где стоит человек с номером (и замыкаем в хоровод); во второй хоровод берём следующие тройки подряд до той включительно, где стоит человек с наименьшим из оставшихся номеров (и замыкаем в хоровод), и так далее.
Обратно, по набору хороводов легко восстановить расстановку: берём хоровод, где стоит человек , находим тройку , в которой он находится, «разрезаем» хоровод сразу за этой тройкой, вытягиваем в линию и ставим в начало расстановки. Далее берём человека с наименьшим номером из оставшихся, находим «его» хоровод, так же разрезаем и подсоединяем к расстановке и т. д.