Разделы 
Дополнительно
Задача по математике - 1182
2018-09-15 
В стране 1993 города, и из каждого выходит не менее 93 дорог. Известно, что из любого города можно проехать по дорогам в любой другой. Докажите, что это можно сделать не более, чем с 62 пересадками. (Дорога соединяет между собой два города.)
Решение:
Докажем утверждение задачи от противного. Пусть найдутся два города A и B такие, что из A в B нельзя проехать, сделав меньше 63 пересадок. Разобьем все города страны на группы следующим образом: нулевая группа состоит из города A, первая — из всех городов, в которые можно проехать из A без пересадок, и так далее (k-я группа состоит из всех городов, в которые можно проехать из A с (k - 1) пересадками, но нельзя с меньшим их числом). Получим не менее 65 групп. Заметим, что при каждом $k = 0, 1, \cdots, 21$ в группах с номерами $3k, 3k + 1$ и $3k + 2$ (или $3k, 3k + 1$, если $(3k + 2)$-й группы не существует) содержится в общей сложности не менее 94 городов, так как из какого-нибудь города $(3k + 1)$-й группы выходит не менее 93 дорог, соединяющих его с городами указанных групп. Следовательно, всего городов в стране не менее, чем $94 \cdot 22 = 2068$, что противоречит условию задачи.
В стране 1993 города, и из каждого выходит не менее 93 дорог. Известно, что из любого города можно проехать по дорогам в любой другой. Докажите, что это можно сделать не более, чем с 62 пересадками. (Дорога соединяет между собой два города.)
Решение:
Докажем утверждение задачи от противного. Пусть найдутся два города A и B такие, что из A в B нельзя проехать, сделав меньше 63 пересадок. Разобьем все города страны на группы следующим образом: нулевая группа состоит из города A, первая — из всех городов, в которые можно проехать из A без пересадок, и так далее (k-я группа состоит из всех городов, в которые можно проехать из A с (k - 1) пересадками, но нельзя с меньшим их числом). Получим не менее 65 групп. Заметим, что при каждом $k = 0, 1, \cdots, 21$ в группах с номерами $3k, 3k + 1$ и $3k + 2$ (или $3k, 3k + 1$, если $(3k + 2)$-й группы не существует) содержится в общей сложности не менее 94 городов, так как из какого-нибудь города $(3k + 1)$-й группы выходит не менее 93 дорог, соединяющих его с городами указанных групп. Следовательно, всего городов в стране не менее, чем $94 \cdot 22 = 2068$, что противоречит условию задачи.
