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

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

Условие

В стране 1993 города, и из каждого выходит не менее 93 дорог. Известно, что из каждого города можно проехать по дорогам в любой другой.
Докажите, что это можно сделать не более, чем с 62 пересадками. (Дорога соединяет между собой два города.)


Решение

Пусть найдутся такие два города A и B, что из A в B нельзя проехать, сделав меньше 63 пересадок. Разобьём все города страны на группы следующим образом: нулевая группа состоит из города A, первая – из всех городов, в которые можно проехать из A без пересадок, и так далее (k-я группа состоит из всех городов, в которые можно проехать из A с  k – 1  пересадкой, но нельзя с меньшим их числом). Получим не менее 65 групп. Заметим, что при каждом  k = 0, 1, ..., 21 в группах с номерами 3k,  3k + 1  и  3k + 2  (или 3k,  3k + 1,  если (3k+2)-й группы не существует) содержится в общей сложности не менее 94 городов, так как из какого-нибудь города (3k+1)-й группы выходит не менее 93 дорог, соединяющих его с городами указанных групп. Следовательно, всего городов в стране не менее чем  94·22 = 2068,  что противоречит условию.

Замечания

Чуть более аккуратные оценки (см., например, здесь) показывают, что диаметр графа с n вершинами, степень каждой из которых не меньше k, не превосходит    В частности, диаметр нашего графа не превосходит 62. Это значит, что достаточно 61 пересадки.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 1993
Этап
Вариант 4
класс
Класс 11
задача
Номер 93.4.11.8

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

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