ДИРИХЛЕ И КРОЛИКИ
Самая распространенная формулировка принципа Дирихле, как ни странно, связана с кроликами:
если в n клетках сидит n+1 кролик, то по крайней мере в одной клетке сидит не менее двух кроликов.
Естественно, что под кроликами и клетками могут пониматься не только голуби и ящики (как в английском варианте формулировки), но и вообще любые объекты, которые в математике принято заменять наборами множеств:
если в множестве А, содержащем n+1 элементов, имеется n элементов, удовлетворяющих каким-либо различным свойствам, то хотя 2 из этих элементов, имеют одинаковое свойство.
Примеры применения принципа Дирихле
1. Пусть диктант писали 30 человек. Вова сделал больше всех ошибок в работе - 13. Покажите, что минимум 3 ученика сделали равное количество ошибок.
Решение всех таких задач начинается с понимания, что мы относим к "клеткам", а что к "кроликам". В данном случае в качестве "кроликов" выступают ученики, а в качестве "клеток" - сделанные ими ошибки.
Если в первую клетку посадить учеников, которые не сделали ни одной ошибки, во вторую - сделавших две ошибки и т.д., а в тринадцатую посадить Вову, то решить задачу можно опять методом от противного:
Пусть среди класса нет учеников, сделавших одинаковое количество ошибок. Тогда в каждой клетке максимум 2 ученика. Т.к. клеток всего 14 (в последней сидит один Вова), то суммарное количество учеников не может превышать 13*2+1=27 человек. Мы пришли к противоречию, т.к. диктант писало 30 ребят.
2. Докажите, что в любой компании есть два человека, имеющих одинаковое число знакомых в этой компании.
Решение. Пусть в компании n человек. Тогда у каждого человека может быть от 0 до n-1 знакомых. Таким образом, количество знакомых может принимать различных значений: 0, 1, 2, …, n-1. Поэтому если бы все n человек имели различное число знакомых, то в компании присутствовало бы по одному человеку, имеющему 0, 1, 2, …, n-1 знакомых. Однако если в компании есть человек, имеющий n-1 знакомых, то он знаком со всеми, и следовательно, в компании не может быть человека, который совсем не имеет знакомых. Полученное противоречие показывает, что в любой компании найдутся два человека с одинаковым числом знакомых.
