Дано: столица и 100 городов соединены дорогами с односторонним движением. Из каждого нестоличного города выходит 20 дорог, и в каждый такой город входит 21 дорога.
Найти: доказать, что в столицу нельзя проехать ни из одного города.
Решение:
Предположим, что из какого-то города можно попасть в столицу.
Так как из каждого нестоличного города выходит 20 дорог, и в каждый такой город входит 21 дорога, то общее количество исходящих дорог равно 100*20 = 2000, а общее количество входящих дорог равно 100*21 = 2100.
Из этого следует, что общее количество входящих дорог больше, чем исходящих, что противоречит условию одностороннего движения. Следовательно, из каждого города невозможно попасть в столицу.
Ответ:
В столицу нельзя проехать ни из одного города.