Олимпиадная задача по теории графов и комбинаторике для 9–11 классов — Индивидуальный путь между городами
Задача
В стране 1001 город, каждые два города соединены дорогой с односторонним движением. Из каждого города выходит ровно 500 дорог, в каждый город входит ровно 500 дорог. От страны отделилась независимая республика, в которую вошли 668 городов. Докажите, что из каждого города этой республики можно доехать до любого другого ее города, не выезжая за пределы республики.
Решение
Предположим, что утверждение неверно; скажем, из города X нельзя добраться до Y по городам республики.
Обозначим через A множество всех городов республики, до которых можно добраться из X по городам республики (включая сам город X), а через B – множество всех остальных её городов (оно непусто, так как содержит Y). Тогда города республики разбились на две группы так, что все дороги между группами направлены от B к A.
Обозначим количество городов в группах A и B через a и b соответственно, a + b = 668. Пусть в A городов не меньше, чем в B, то есть a ≥ 334 ≥ b. В B есть город Z, из которого выходит не менее b–1/2 дорог в города из B.
Кроме того, из Z выходит a дорог к городам группы A. Значит, из Z выходит не менее 
дорог. Противоречие.
Случай, когда в B больше городов, чем в A, рассматривается аналогично.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь