Разделы 
Дополнительно
Задача по математике - 2019
2019-01-23 
В стране 1001 город, любые два города соединены дорогой с односторонним движением. Из каждого города выходит ровно 500 дорог, в каждый город входит ровно 500 дорог. От страны отделилась независимая республика, в которую вошли 668 городов. Докажите, что из любого города этой республики можно доехать до любого другого ее города, не выезжая за пределы республики.
Решение:
Предположим, что утверждение задачи неверно; скажем, из города $X$ нельзя добраться до $Y$ по городам республики ($X, Y$ - города республики). Обозначим через $A$ множество всех городов республики, до которых можно добраться из $X$ по городам республики (включая сам город $X$), а через $B$ - множество всех остальных ее городов (оно непусто, так как содержит $Y$). Тогда города республики разбились на две группы так, что все дороги между городами группы $A$ и группы $B$ направлены от $B$ к $A$.
Обозначим количество городов в группах $A$ и $B$ через $a$ и $b$ соответственно, $a + b = 668$. Пусть в $A$ городов не меньше, чем в $B$, т. е. $a \geq 334 \geq b$. В $В$ есть город $Z$, из которого выходит не менее $\frac{b-1}{2}$ дорог в города из $B$. Кроме того, из $Z$ выходит $a$ дорог к городам группы $A$. Всего дорог, выходящих из $Z$, получается не менее $a + \frac{b-1}{2} = \frac{a + (a + b) - 1}{2} = \frac{a + 667}{2} \geq \frac{1001}{2} > 500$. Противоречие.
Случай, когда в $B$ больше городов, чем в $A$, рассматривается аналогично путем выбора города из $А$, в который входит не менее $\frac{a-1}{2}$ дорог из городов из $A$.
В стране 1001 город, любые два города соединены дорогой с односторонним движением. Из каждого города выходит ровно 500 дорог, в каждый город входит ровно 500 дорог. От страны отделилась независимая республика, в которую вошли 668 городов. Докажите, что из любого города этой республики можно доехать до любого другого ее города, не выезжая за пределы республики.
Решение:
Предположим, что утверждение задачи неверно; скажем, из города $X$ нельзя добраться до $Y$ по городам республики ($X, Y$ - города республики). Обозначим через $A$ множество всех городов республики, до которых можно добраться из $X$ по городам республики (включая сам город $X$), а через $B$ - множество всех остальных ее городов (оно непусто, так как содержит $Y$). Тогда города республики разбились на две группы так, что все дороги между городами группы $A$ и группы $B$ направлены от $B$ к $A$.
Обозначим количество городов в группах $A$ и $B$ через $a$ и $b$ соответственно, $a + b = 668$. Пусть в $A$ городов не меньше, чем в $B$, т. е. $a \geq 334 \geq b$. В $В$ есть город $Z$, из которого выходит не менее $\frac{b-1}{2}$ дорог в города из $B$. Кроме того, из $Z$ выходит $a$ дорог к городам группы $A$. Всего дорог, выходящих из $Z$, получается не менее $a + \frac{b-1}{2} = \frac{a + (a + b) - 1}{2} = \frac{a + 667}{2} \geq \frac{1001}{2} > 500$. Противоречие.
Случай, когда в $B$ больше городов, чем в $A$, рассматривается аналогично путем выбора города из $А$, в который входит не менее $\frac{a-1}{2}$ дорог из городов из $A$.
