Выбрано 5 задач 
Убрать все задачи
На книжной полке стоят 30 томов энциклопедии в некотором порядке. За одну операцию разрешается менять местами любые два соседних тома. За какое наименьшее число операций можно гарантированно выстроить все тома в правильном порядке (с первого по тридцатый слева направо) независимо от начального положения?
Жили-были двадцать шпионов. Каждый из них написал донос на десять своих коллег.
Докажите, что не менее, чем десять пар шпионов донесли друг на друга.
В прямоугольном треугольнике ABC (∠B = 90°) проведена высота BH. Окружность, вписанная в треугольник ABH, касается сторон AB, AH в точках H1, B1 соответственно; окружность, вписанная в треугольник CBH, касается сторон CB, CH в точках H2, B2 соответственно. Пусть O – центр описанной окружности треугольника H1BH2. Докажите, что OB1 = OB2.
В ориентированном графе 101 вершина. У каждой вершины число входящих и число выходящих рёбер равно 40.
Доказать, что из каждой вершины можно попасть в любую другую, пройдя не более чем по трём ребрам.
В стране есть n > 1 городов, некоторые пары городов соединены двусторонними беспосадочными авиарейсами. При этом между каждыми двумя городами существует единственный авиамаршрут (возможно, с пересадками). Мэр каждого города X подсчитал количество таких нумераций всех городов числами от 1 до n, что на любом авиамаршруте, начинающемся в X, номера городов идут в порядке возрастания. Все мэры, кроме одного, заметили, что их результаты подсчётов делятся на 2016. Докажите, что и у оставшегося мэра результат также делится на 2016.
|
|
 |
Условие
В стране есть 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 из нумерации, подходящей для чётного города, получается нумерация, подходящая для нечётного (и наоборот). Это сопоставление взаимно однозначно. Значит, тех и других нумераций поровну.
