При решении нестандартных задач, где требуется что-нибудь доказать, часто бывает полезен так называемый "принцип Дирихле".
Самый простой и понятный способ формулирования этого принципа выглядит так :
"Нельзя посадить семерых зайцев в три клетки так, чтобы в каждой клетке находилось не больше двух зайцев."
Чтобы было понятно на сколько важен этот принцип, мы решим несколько задач, выбирая каждый раз подходящих "зайцев" и строя соответствующие "клетки".
1. В классе 30 человек. В диктанте Стас Иванов сделал 13 ошибок, а остальные - меньше. Докажите, что по крайней мере три ученика сделали ошибок поровну (может быть, по 9 ошибок).
Это доказывается с помощью принципа Дирихле. Подумайте, кто здесь зайцы, и где клетки. Здесь "зайцы" - ученики, а "клетки" - число сделанных ошибок.
В клетку 0 "посадим" всех, кто не сделал ни одной ошибки, в клетку 1 - тех, у кого одна ошибка, в клетку 2 - две, ... и так до клетки 13, куда попал один Стас Иванов.
Теперь применим принцип Дирихле (обратите внимание - это очень важное место).
Докажем утверждение задачи от противного.
Предположим, никакие три ученика не сделали по одинаковому числу ошибок, то есть в каждую из клеток 0, 1,..., 12 попало меньше трех школьников.
Тогда в каждой из них два человека или меньше, а всего в этих 13 клетках не больше 26 человек.
Добавив Стаса Иванова, все равно не наберем 30 ребят. Противоречие.
Можно ли утверждать, что ровно трое сделали поровну ошибок ? Нет, конечно.
Возможно, что все ребята, кроме Стаса, написали диктант без единой ошибки, то есть, все сделали по 0 ошибок.
Можно ли считать, что по крайней мере четверо попали в одну "клетку" ? Нет, нельзя.
Класс, в котором по 3 человека сделали 0, 1, 2 ошибки, по 2 человека - 3, 4, ..., 12 ошибок и один - 13, удовлетворяет условию задачи.
2. Пусть в классе 41 человек, а не 30. Докажите, что найдутся четверо, сделавшие одинаковое число ошибок. (Остальные условия - как в задаче 1).
3. В Москве около 7,1 миллиона жителей, на голове у каждого не больше 100 000 волос. Докажите, что в Москве есть по крайней мере 70 тысяч человек с одинаковым числом волос на голове.
Знакомства. Будем считать, что знакомство - "симметричное" отношение между людьми : если Комаров знаком с Жуковым, то и Жуков знаком с Комаровым.
4. Выберем любым образом 5 человек . Докажите, что по крайней мере двое из них имеют одинаковое число знакомых среди выбранных.
