А. И. Орлов

"Клетки" и "зайцы" При решении задач "на доказательство" часто бывает полезен так называемый "принцип Дирихле" *). В самой простой и несерьезной форме он выглядит так : "нельзя посадить семерых зайцев в три клетки так, чтобы в каждой клетке находилось не больше двух зайцев. Сейчас мы решим несколько задач, выбирая каждый раз подходящих "зайцев" и строя соответствующие "клетки". 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 человек . Докажите, что по крайней мере двое из них имеют одинаковое число знакомых среди выбранных. стр.1 2 *) Петер Густав Лежен Дирихле (1805-1859)- известный немецкий ученый.