Деревья и остовные деревья
Ошибка.
Попробуйте повторить позже
В стране есть городов, некоторые пары городов соединены двусторонними беспосадочными авиарейсами. При этом между любыми
двумя городами существует единственный авиамаршрут (возможно, с пересадками). Мэр каждого города
подсчитал количество таких
нумераций всех городов числами от
до
что на любом авиамаршруте, начинающемся в
номера городов идут в порядке
возрастания. Все мэры, кроме одного, заметили, что их результаты подсчетов делятся на
Докажите, что и у оставшегося мэра
результат также делится на
Источники:
Подсказка 1:
Попробуйте получить некоторое равенство, включающее в себя числа, полученные мэрами, чтобы потом сказать, что раз все слагаемые, кроме одного, кратны 2016, то и последнее кратно.
Подсказка 2:
Назовём некоторый город А столицей. Назовём город чётным, если маршрут из A до него содержит чётное количество рейсов. Иначе нечётным. Докажите, что сумма чисел у нечётных городов равна сумме чисел у чётных.
Подсказка 3:
Попробуйте некоторым образом взаимно однозначно сопоставить нумерации для нечётных и чётных городов.
Подсказка 4:
Пусть некоторая нумерация была посчитана мэром города X. Какой номер в ней имеет X?
Подсказка 5:
Он имеет номер 1. Теперь рассмотрите любую нумерацию, подходящую чётному городу E. Пусть номер 2 имеет город W. Попробуйте подобрать нумерацию, подходящую для W.
Подсказка 6:
Что, если поменять номера 1 и 2?
Назовём какой-нибудь город столицей. Назовём город чётным, если маршрут из
до него содержит чётное число рейсов, и нечётным
иначе (таким образом, город
чётный). Тогда чётность любых двух городов, соединённых рейсом, различна. Мы докажем, что сумма
чисел, полученных мэрами чётных городов, равна сумме чисел, полученных мэрами нечётных; из этого следует утверждение
задачи.
Назовём нумерацию городов подходящей для города если мэр города
её посчитал. Ясно, что в любой нумерации, подходящей
городу
он имеет номер
так что каждая нумерация подходит не более, чем одному городу.
Рассмотрим любую нумерацию, подходящую чётному городу Пусть номер
в ней носит город
тогда
— нечётный город,
соединённый с
иначе на маршруте от
до
встретился бы город с большим номером. Поменяем местами номера
и
мы
получим нумерацию, в которой номер
носит нечётный город
Рассмотрим любой маршрут начинающийся в
Он получается из некоторого маршрута, выходящего из
либо добавлением
города
в начало (если
проходит через
), либо откидыванием
из начала (в противном случае). Тогда легко видеть, что после
обмена
и
номера на
идут в порядке возрастания.
Итак, после перемены номеров и
из нумерации, подходящей для чётного города, получается нумерация, подходящую для
нечётного (и наоборот). Это сопоставление взаимно однозначно. Значит, тех и других нумераций поровну, что и требовалось
доказать.
Специальные программы

Программа
лояльности вер. 2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к твоему аккаунту.

Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас важно быть полезными учителям по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

