Задание №163617: Дроби

6

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

Другоерешение. Приведёмрешение,использующеелинейнуюалгебру.Воизбежаниепе-
регрузки слова «номер» будем называть гостиничные номера комнатами.
Занумеруем математиков числами от 1 до 𝑎𝑏; комнаты тоже занумеруем числами от 1 до
𝑎𝑏, причём так, чтобы этажи соответствовали последовательным блокам чисел. Постро-
им матрицу 𝑀 размера 𝑎𝑏 × 𝑎𝑏, где число 𝑀 в 𝑖-й строке и 𝑗-м столбце определяется
𝑖,𝑗
следующим образом:
1, если 𝑖-му математику нравится 𝑗-я комната;
𝑀 = {
𝑖,𝑗
0, иначе.
Расселениеможнопредставитькакперестановку𝜎 ∈ 𝑆 (т.е.функцию𝜎∶ {1,2,…,𝑎𝑏} →
𝑎𝑏
{1,2,…,𝑎𝑏}),сопоставляющуюномеруматематиканомеркомнаты.Тогдаколичествопод-
ходящих расстановок равно перманенту матрицы 𝑀:
𝑎𝑏
perm(𝑀) = ∑ (∏𝑀 ).
𝑖,𝜎(𝑖)
𝜎∈𝑆𝑎𝑏 𝑖=1
Действительно, если данная перестановка 𝜎 подходит, то все сомножители 𝑀 будут
𝑖,𝜎(𝑖)
равны 1, а если не подходит, то хотя бы один из сомножителей равен 0.
Таккакнасинтересуеттолькочётностьвыражения,томожнопроизвольноменятьзнаки
передслагаемыми.Заменивзнакпередкаждымпроизведениемначётностьперестанов-
ки sgn(𝜎) = ±1, получим определитель матрицы 𝑀:
𝑎𝑏
det(𝑀) = ∑ (sgn(𝜎) ⋅ ∏𝑀 ).
𝑖,𝜎(𝑖)
𝜎∈𝑆𝑎𝑏 𝑖=1