МОШ 2026, 11 класс, задача 4
В гостинице этажей, на каждом этаже одноместных номеров. На математический конгресс приехало математиков. Оказалось, что каждому математику на каждом этаже нравится ровно один номер. Докажите, что число способов поселить всех математиков в гостиницу так, чтобы каждому нравился его номер, чётно.
(В. Ретинский)
Решение. Зафиксируем произвольное расселение на всех этажах выше второго. Покажем, что количество способов дополнить его до расселения всех математиков чётно.
Построим граф, в котором вершин соответствуют номерам на первых двух этажах. Для каждого математика проведём ребро, соединяющее два подходящих ему номера. Получим граф , в котором вершин и рёбер.
Если в графе есть висячая вершина , то в соответствующий номер можно поселить только одного математика. Поселим математика в этот номер (в любом подходящем расселении он живёт в этом номере), а из графа удалим вершину и исходящее из неё ребро.
Будем продолжать процесс, пока в графе не останется висячих вершин. После завершения процесса мы получим непустой граф . Если в графе есть изолированная вершина , то расселение невозможно, поскольку мы получили, что в некотором номере при любом подходящем расселении не живёт ни одни математик. Тогда количество способов расселить всех равно , что является чётным числом.
Иначе в графе степень каждой вершины не меньше двух. Заметим, что в графе поровну вершин и рёбер, так как их изначально поровну, и каждым шагом мы удаляем одну вершину и одно ребро. Отсюда следует, что степени всех вершин равны двум. Из леммы о хороводах следует, что граф является объединением нескольких непересекающихся циклов. Нетрудно видеть, что для каждого цикла есть ровно два способа сопоставить вершинам-номерам рёбра-математиков. Действительно, при выборе номера для одного из математиков, расселение остальных математиков данного цикла определяется однозначно. Тогда если граф состоит из циклов, то количество способов расселить математиков равняется , что является чётным числом.
Мы доказали, что для каждого выбора расселения во все дни после второго количество способов дополнить его до полного расселения чётно. Осталось просуммировать полученные величины по всем выборам расселения во все дни после второго. С одной стороны, мы получим искомое количество способов расселить всех. С другой стороны, так как сумма чётных чисел чётна, то результат будет чётным.
Замечание. Приведём альтернативное красивое доказательство чётности числа расселений математиков, использующее линейную алгебру.
Занумеруем математиков числами от до ; номера гостиницы на -м этаже () занумеруем числами от до . Построим матрицу размера , где число в -й строке и -м столбце определяется следующим образом:
Расселение математиков по номерам можно представить как перестановку (т. е. функцию ), сопоставляющую номеру математика его номер в гостинице. Тогда количество подходящих расселений равно перманенту матрицы :
Действительно, если данная перестановка подходит, то произведение чисел будет равно , иначе .
Так как нас интересует только чётность данного выражения, то можно произвольным образом менять знаки перед слагаемыми. Заменив знак перед каждым произведением на чётность перестановки , получим определитель матрицы :
Теперь заметим, что сумма первых столбцов матрицы (соответствующих первому этажу гостиницы) равна столбцу из единиц, так как каждому математику нравится ровно один номер на первом этаже гостиницы. Такая же сумма у следующих столбцов матрицы. Следовательно, столбцы матрицы линейно зависимы, то есть она вырожденная; а так как определитель любой вырожденной матрицы равен нулю, то он чётен.