|
|
 |
Условие
В стране есть n > 1 городов, некоторые пары городов соединены двусторонними беспосадочными авиарейсами. При этом между каждыми двумя городами существует единственный авиамаршрут (возможно, с пересадками). Мэр каждого города X подсчитал количество таких нумераций всех городов числами от 1 до n, что на любом авиамаршруте, начинающемся в X, номера городов идут в порядке возрастания. Все мэры, кроме одного, заметили, что их результаты подсчётов делятся на 2016. Докажите, что и у оставшегося мэра результат также делится на 2016.
Решение
Назовём какой-нибудь город A столицей. Назовём город чётным, если маршрут из A до него содержит чётное число рейсов, и нечётным иначе (таким образом, город A чётный). Тогда чётность любых двух городов, соединённых рейсом, различна. Мы докажем, что сумма чисел, полученных мэрами чётных городов, равна сумме чисел, полученных мэрами нечётных; из этого следует утверждение задачи.
Назовём нумерацию городов подходящей для города X, если мэр города X её посчитал. Ясно, что в любой нумерации, подходящей городу X, он имеет номер 1, так что каждая нумерация подходит не более чем одному городу.
Рассмотрим любую нумерацию, подходящую чётному городу E. Пусть номер 2 в ней носит город W; тогда W – нечётный город, соединённый с E, иначе на маршруте от E до W встретился бы город с бóльшим номером. Поменяв местами номера 1 и 2, мы получим нумерацию, в которой номер 1 носит нечётный город W.
Рассмотрим любой маршрут m, начинающийся в W. Он получается из некоторого маршрута, выходящего из E, либо добавлением города W в начало (если m проходит через E), либо откидыванием E из начала (в противном случае). Отсюда следует, что после обмена 1 и 2 номера на m идут в порядке возрастания.
Итак, после перемены номеров 1 и 2 из нумерации, подходящей для чётного города, получается нумерация, подходящая для нечётного (и наоборот). Это сопоставление взаимно однозначно. Значит, тех и других нумераций поровну.
