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

Докажем от обратного.

Пусть из каждого города выходит различное количество дорог.

Тогда, максимальное количество дорог, выходящее из одного любого города может быть равно 238, а минимальное 1, так как из города не может выходить меньше одной дороги.

В этом случае получается, что от 1 до 238 городов имеют различное количество дорог.

Но городов 239, а не 238.

Значит, у 239-го города будет столько же дорог, что и у одного из 238-ми городов.

Таким образом, есть два города, из которых выходит одинаковое количество дорог.