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

А принцип Дирихле немножко) к другим задачам применяется....комбинаторика....

В любом случае, спасибо за старание.

Почему не совсем?) Представляем города в виде "кроликов" и кол-во возможных дорог от каждого города в виде "клеток". Вот вам и принцип Дирихле в чистом виде)

только не в этой задаче... это на графы.

Агаханов ( надеюсь слышали кто это): чтобы уверенней решать такие задачи, начните с Кенигсбергских Мостов. А мосты как всем известно - это Эйлеровы графы.

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