Question

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

Answer 1

В городе всего 13 городов⇒от каждого города может выходить от 0 до 12 дорог. Заметим, что если от какого-то города выходит 12 дорог, то ни от одного другого не может выходить 0 дорог, т.к. у него уже есть минимум одна дорога. Также и наоборот, если есть город, у которого 0 дорог, то не может существовать города, у которого было бы 12 дорог. Поэтому в каждой комбинации дорог с городами мы имеем 13 городов, от каждого из которых могут выходить дороги лишь 12 способами (Либо от 0 до 11, либо от 1 до 12).
Кол-во способов выхода дорог меньше, чем количество городов(12<13), поэтому обязательно найдутся два города, из которых выходит поровну дорог, ч.т.д.  
((Данный вывод очевиден благодаря Принципу Дирихле: Если в N клетках сидит N+1 кроликов, то обязательно найдётся клетка, которой сидит два кролика. В нашем случае N=12(кол-во способов), а N+1=13(кол-во городов). Если ты хочешь узнать больше про Принцип Дирихле, то можешь обратиться к сторонней литературе. Есть даже отдельные книги, посвящённые данному принципу.))