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(кол-во городов). Если ты хочешь узнать больше про Принцип Дирихле, то можешь обратиться к сторонней литературе. Есть даже отдельные книги, посвящённые данному принципу.))

Answer 2

Предположим, что каждый город соединен с разным количеством дорог. Поскольку в стране всего 13 городов, количество дорог, выходящих из каждого города, может быть от 0 до 12.

Предположим также, что ни один город не имеет 0 или 12 дорог. Это означает, что каждый город имеет от 1 до 11 дорог, включительно.

Если рассмотреть все 13 городов, то общее количество дорог будет равно сумме количества дорог, выходящих из каждого города. Так как каждое количество дорог от 1 до 11 включительно встречается ровно один раз, общее количество дорог должно быть однозначно определено.

Однако это противоречит условию, что некоторые города соединены дорогами. Если бы каждый город имел разное количество дорог, общее количество дорог было бы уникальным.

Таким образом, наше предположение неверно, и существуют два города, из которых выходит поровну дорог.