Олимпиада имени Леонарда Эйлера 2017-2018 учебный год, I тур регионального этапа

В Тридесятом царстве из каждого города выходит по 30 дорог, причём каждая дорога соединяет два города, не проходя через другие города. Тридесятый царь захотел разместить в некоторых городах по дорожно-эксплуатационному управлению (ДЭУ), обслуживающему все выходящие из города дороги, так, чтобы каждая дорога обслуживалась хотя бы одним управлением и управления были размещены не более чем в половине городов. Может ли так оказаться, что у царя существует ровно 2018 способов сделать это? ( И. Богданов, С. Берлов )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Ответ. Не может.
Решение. Если желание царя невыполнимо, то всё уже доказано. Далее считаем, что оно выполнимо. Возьмём любое удовлетворяющее требованиям царя размещение ДЭУ. Пусть $S$ --- общее число дорог в царстве. Так как каждая дорога соединяет два города, число городов в царстве равно $2S/30.$ Поэтому управлений должно быть не более, чем $S/30.$ С другой стороны, так как каждое управление обслуживает 30 дорог, управлений должно быть не менее, чем $S/30.$ Поэтому их ровно $S/30,$ откуда следует, что каждая дорога обслуживается ровно одним управлением и управления находятся ровно в половине городов.
Закроем все ДЭУ в городах, где они есть, и откроем ДЭУ в каждом городе, где его не было. Тогда по-прежнему у каждой дороги один конец будет в городе с ДЭУ, а другой --- в городе без ДЭУ, то есть каждая дорога будет обслуживаться ровно одним управлением, причём, как было доказано выше, городов с ДЭУ будет ровно половина. Очевидно, если проделать описанную процедуру второй раз, получится исходное расположение ДЭУ. Таким образом, все способы размещения ДЭУ разбиваются на пары.
Заметим теперь, что создание ДЭУ в одном городе однозначно определяет наличие или отсутствие ДЭУ во всех городах, в которые из него можно проехать по дорогам, так как на любом пути города с ДЭУ и без ДЭУ должны чередоваться. Поэтому если в царстве можно добраться от любого города до любого, то существует ровно два способа разместить ДЭУ. В противном случае царство можно разбить на графства так, что в каждом графстве от любого города можно добраться до любого, а между графствами дорог нет. В каждом графстве можно выбрать один из двух способов размещения ДЭУ независимо от остальных, и потому если графств $n,$ ДЭУ можно разместить $2^n$ способами. Так как число 2018 не является степенью двойки, то ровно 2018 способов разместить ДЭУ быть не может.