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

203

264

Посмотреть ответы 2

Ответы на вопрос:

PomogyBratan

Математика

4,8(22 оценок)

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