Олимпиадная задача о столице и дорогах с односторонним движением
В некоторой стране есть столица и еще 100 городов. Некоторые города (в том числе и столица) соединены дорогами с односторонним движением. Из каждого нестоличного города выходит 20 дорог, и в каждый такой город входит 21 дорога. Докажите, что в столицу нельзя проехать ни из одного города.
Разобрать решение
Пусть в столицу входит a дорог. Тогда общее число "входящих" дорог равно 21·100 + a, а общее количество "выходящих" дорог не больше
20·100 + (100 – a). Поэтому 21·100 + a ≤ 20·100 + (100 – a), то есть 2a ≤ 0. Таким образом, a = 0.
Обсуждение
0Комментариев пока нет.
Чтобы оставить комментарий, войдите в аккаунт.