ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 65762
Темы:    [ Теория графов (прочее) ]
[ Делимость чисел. Общие свойства ]
[ Четность и нечетность ]
[ Мощность множества. Взаимно-однозначные отображения ]
Сложность: 4
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

Автор: Петров Ф.

В стране есть  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 из нумерации, подходящей для чётного города, получается нумерация, подходящая для нечётного (и наоборот). Это сопоставление взаимно однозначно. Значит, тех и других нумераций поровну.

Источники и прецеденты использования

олимпиада
Название Всероссийская олимпиада по математике
год
Вариант 2015/2016
этап
Вариант 5
класс
Класс 11
задача
Номер 11.6

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .