В стране 13 городов.Некоторые из них соединены дорогами. Доказать, что есть два города, из которых выходит поровну дорог.

Для ответа на этот вопрос, воспользуемся принципом Дирихле. Принцип Дирихле гласит, что если объекты распределяются по ящикам, и объектов больше, чем ящиков, то по крайней мере в одном ящике окажется больше одного объекта.

В данном случае, объектами являются дороги, а ящиками — количество дорог, выходящих из каждого города. Поскольку городов 13, то возможные количества дорог, выходящих из каждого города, могут быть от 0 до 12. То есть, "ящиков" на самом деле 13.

Теперь докажем, что найдутся по крайней мере два города с одинаковым количеством выходящих дорог.

1. Если предположить, что из каждого города выходит разное количество дорог, то количество дорог, выходящих из каждого города, должно быть все целые числа от 0 до 12. Однако, это невозможно, так как если из одного города выходит 12 дорог, то каждая из этих дорог должна вести в разные города. Но у нас всего 13 городов, и один из них — это город, из которого эти дороги начинаются. Следовательно, максимальное количество дорог, выходящих из одного города, может быть 12 только в том случае, если из всех остальных городов не выходит ни одной дороги, что противоречит нашему предположению о том, что из каждого города выходит разное количество дорог.

2. Если в стране есть города, из которых не выходят дороги (например, 0 дорог), то максимальное количество дорог, выходящих из одного города, может быть только 11 (поскольку один город уже "занят" нулевым количеством дорог). Это уменьшает количество возможных "ящиков" (количеств дорог), делая невозможным размещение всех 13 городов по разным "ящикам" без повторения.

Таким образом, по принципу Дирихле, в нашем случае обязательно найдутся по крайней мере два города, из которых выходит одинаковое количество дорог.