|
|
 |
Условие
В стране 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 пересадки.
