МОШ 2026, 9 класс, задача 6

Решение. Будем называть этажи, кроме первых двух, верхними. Зафиксируем произвольное расселение на всех верхних этажах. Покажем, что количество способов дополнить его до полного расселения чётно.

Построим граф, в котором вершин соответствуют номерам на первых двух этажах. Для каждого математика, которого мы не поселили на верхних этажах, проведём ребро, соединяющее два подходящих ему номера. Получим граф , в котором вершин и рёбер.

Если в графе есть вершина степени , то в соответствующий номер можно поселить только одного математика. Поселим математика в этот номер, а из графа удалим вершину и исходящее из неё ребро. Будем делать такие шаги, пока в графе остаются висячие вершины.

В итоге мы получим непустой граф . Действительно, рассмотрим самую последнюю удаленную висячую вершину — исходящее из неё ребро соединяло её с другой вершиной, которая уже не могла быть удалена; то есть хотя бы одна вершина в должна остаться.

Если в графе найдётся изолированная вершина , то в некотором номере не сможет жить ни один математик. Тогда количество способов расселить всех равно , что является чётным числом.

В ином случае в графе нет вершин степени и , то есть степень каждой вершины не меньше . Отсюда следует, что суммарная степень всех вершин не меньше удвоенного количества вершин. С другой стороны, вершин и рёбер поровну, так как изначально в графе их было поровну, а каждым шагом мы удаляли одну вершину и одно ребро. Значит, суммарная степень вершин (всегда равная удвоенному количеству рёбер) в точности равна удвоенному количеству вершин. Отсюда следует, что степени всех вершин равны .

Тогда граф является объединением нескольких непересекающихся циклов. (Это утверждение, известное как лемма о хороводах, следует из того, что если выйти из любой вершины, то можно единственным способом идти по ребрам и зациклиться; таким образом каждой вершине сопоставляется единственный содержащий её цикл.) Нетрудно видеть, что для каждого цикла есть ровно два способа сопоставить вершинам-номерам рёбра-математиков: если цикл нарисовать по кругу, то можно либо каждой вершине сопоставить правое ребро, либо каждой — левое. Тогда если граф состоит из циклов, то количество способов расселить математиков равно , что является чётным числом.

Мы доказали, что если фиксировать расселение во всех верхних этажах, то количество способов дополнить его до полного расселения чётно. Осталось просуммировать полученные величины по всем способам расселения в верхних этажах. С одной стороны, мы получим искомое количество способов расселить всех. С другой стороны, так как сумма чётных чисел чётна, то результат будет чётным.

Комментарий. Эту идею можно реализовать и иначе, напрямую построив разбиение расселений на пары. Рассмотрим произвольное расселение и построим ориентированный граф, вершинами которого будут номера первых двух этажей; ребро выходит из номера в номер на другом этаже, если математику, живущему в , нравится .

Из каждой вершины, таким образом, выходит ровно одно ребро. Значит, мы можем выйти из любой вершины и идти по рёбрам, пока не зациклимся (не обязательно при этом вернувшись в исходную). Если вершина участвует в цикле, то цикл восстанавливается однозначно (можно просто начать из данной вершины и идти по рёбрам); следовательно, циклы не пересекаются.

Из всех циклов выберем тот, в который мы придём, начав из первого номера первого этажа. Этот цикл будем называть главным. Заметим, что если мы переселим каждого математика в главном цикле в следующий номер по циклу (в направлении ориентированных рёбер), то мы получим ещё одно корректное расселение. При этом сам главный цикл останется циклом — лишь поменяются направления всех его рёбер. Математики вне цикла остались на месте, поэтому остальные рёбра сохранятся. Значит, если мы в новом расселении выберем главный цикл, он будет тем же самым (только с перевёрнутыми рёбрами). Применив переселение ещё раз, мы вернёмся в исходное расселение.

Таком образом, каждое расселение сопоставлено другому, причём сопоставление взаимно. Такое сопоставление разбивает все расселения на пары, откуда следует, что их чётно.

Другое решение. Приведём решение, использующее линейную алгебру. Во избежание перегрузки слова «номер» будем называть гостиничные номера комнатами.

Занумеруем математиков числами от до ; комнаты тоже занумеруем числами от до , причём так, чтобы этажи соответствовали последовательным блокам чисел. Построим матрицу размера , где число в -й строке и -м столбце определяется следующим образом:

Расселение можно представить как перестановку (т. е. функцию ), сопоставляющую номеру математика номер комнаты. Тогда количество подходящих расстановок равно перманенту матрицы :

Действительно, если данная перестановка подходит, то все сомножители будут равны , а если не подходит, то хотя бы один из сомножителей равен .

Так как нас интересует только чётность выражения, то можно произвольно менять знаки перед слагаемыми. Заменив знак перед каждым произведением на чётность перестановки , получим определитель матрицы :

Теперь заметим, что векторная сумма столбцов матрицы, соответствующих комнатам первого этажа, равна столбцу из единиц, так как у каждого математика есть ровно одна комната на этом этаже, которая ему нравится. Такая же сумма у столбцов матрицы, соответствующих второму этажу. Следовательно, столбцы матрицы линейно зависимы, то есть она вырожденная; а так как определитель любой вырожденной матрицы равен нулю, то он чётен.