Принцип Дирихле

         Принцип Дирихле  имеет несколько формулировок. Наиболее простая следующая: «Если пять кроликов сидят в двух клетках, то в некоторой клетке сидит не менее трех кроликов». В обобщенной формулировке принцип Дирихле звучит так: «Если в k клетках больше nk кроликов, то хотя бы в одной сидит больше n кроликов». Немного иначе это утверждение формулируется так: «Если n кроликов сидят в k клетках, то найдется клетка, в которой сидит не меньше чем n/k кроликов, и найдется клетка, в которой сидит не больше чем n/k кроликов». Пусть вас не смущает дробное число кроликов: в первой формулировке получится, что в клетке сидит не менее 5/2 кроликов, значит, не меньше трех.

Принцип Дирихле известен также как принцип голубей и ящиков, когда роль кроликов играют голуби, а клеток – ящики. Это название распространено в английском и некоторых других языках.

Доказательство принципа Дирихле простое, но заслуживает внимания, поскольку похожие рассуждения часто встречаются. 

Проведем доказательство методом от противного для обобщенной формулировки принципа Дирихле. Предположим противное: в каждой клетке сидит не более k кроликов. Тогда всего кроликов не более nk, а их по условию больше nk. Получили противоречие, которое опровергает наше предположение. Принцип Дирихле кажется очевидным, однако, чтобы его применить, бывает не просто догадаться, что считать кроликами, а что – клетками. Можно дать такой совет: если каждому элементу множества A соответствует ровно один элемент множества B, то элементы A можно назвать кроликами, а элементы B – клетками.

Принцип Дирихле бывает непрерывным: «Если n кроликов съели m кг травы, то какой-то кролик съел не меньше m/n кг и какой-то съел не больше m/n кг» (а если кто-то съел больше среднего, то кто-то съел меньше среднего). Заметим, что в этой формулировке кролики играют роль клеток для травы, а трава – роль кроликов, сидящих в клетках.

 Задача 17. В классе 40 учеников. Найдется ли такой месяц в году, в котором отмечают свой день рождения не меньше чем 4 ученика этого класса?

Решение (метод от противного). Предположим, что такой месяц не найдется. Тогда в каждом из 12 месяцев года отмечают свой день рождения не более трех одноклассников. В этом случае учащихся всего не более 12*3 = 36, что противоречит условию задачи.

Наше предположение неверно, значит, найдется месяц, в котором день рождения не менее чем у четырех учеников этого класса.

Решение (с использованием принципа Дирихле). Докажем, что такой месяц найдется. Поскольку каждому ученику соответствует ровно один месяц, в котором он родился, то роль «клеток» играют месяцы года (их 12), а роль «кроликов» – учащиеся (их 40). По принципу Дирихле найдется клетка, в которой сидит не менее чем 40/12 кроликов, т.е. 4 кролика. Следовательно, найдется месяц в году, в котором не менее 4 учащихся класса отмечают свой день рождения.

 Задача 18. В Москве живет около 10 млн. жителей , на голове у каждого не более 150 000 волос. Докажите, что в Москве есть по крайней мере 60 человек с одинаковым числом волос на голове.

Решение. Поскольку каждому жителю Москвы соответствует определенное количество волос на голове, то жители будут играть роль зайцев, а количество волос – роль клеток (их 150 001: можно пронумеровать от 0 до 150 001), каждый «кролик» попадает в ту «клетку», которая соответствует количеству волос у него на голове.

Поскольку в 150 001 «клетке» сидит более 59*150001=8850059 «кроликов», значит хотя бы в одной сидит не менее 60 «кроликов». Следовательно, по принципу Дирихле, в Москве есть по крайней мере 60 человек с одинаковым числом волос на голове.

При решении задачи 18 иногда допускается ошибка: количество возможных вариантов («клеток») считают равным 150 000, забывая о допустимом варианте 0 волос.

 Задача 19.  В первенстве по футболу участвуют 12 команд, каждые две из них должны сыграть между собой один матч. Докажите, что в любой момент состязаний имеются две команды, сыгравшие одинаковое число матчей.

Решение. Количество матчей, сыгранное каждой командой, изменяется от 0 (в начале первенства) до 11 (в конце первенства). Если предположить, что к какому-то моменту состязаний все команды сыграли разное количество матчей, то это означает, что одна команда еще не сыграла ни одного матча, вторая – 1, третья – 2, …, двенадцатая – все 11 матчей. Тогда получается, что двенадцатая команда сыграла уже со всеми командами, а первая – ни с одной. Получили противоречие. Следовательно, в любой момент состязаний хотя бы две команды сыграли равное количество матчей.

 Задачи.

20. В школе 30 классов и 1000 учащихся. Докажите, что есть класс, в котором не менее 34 учеников.

21. В классе учится 22 ученика. а) Докажите, что найдутся два ученика, родившихся в одном месяце. б) Обязательно ли найдутся три таких ученика?

22. В классе 30 учеников. В диктанте Вова сделал 13 ошибок, а остальные – меньше. Докажите, что по крайней мере три ученика сделали одно и то же количество ошибок.

23. Числа от 1 до 10 записали в строчку в произвольном порядке и каждое из них сложили с его порядковым номером. Могли ли все полученные суммы оканчиваться разными цифрами?

24. 15 ребят собрали 100 орехов. Докажите, что какие-то два из них собрали одинаковое число орехов.

25. Докажите, что из любых 12 натуральных чисел можно выбрать два, разность которых делится на 11.

26. Докажите, что из любых n + 1 натуральных чисел можно выбрать два, разность которых делится на n .

27. Тридцать студентов с пяти курсов придумали 40 задач для олимпиады, причем однокурсники – одинаковое количество задач, а студенты с разных курсов – разное. Сколько студентов придумали по одной задаче?

28. На собеседование пришли 65 школьников. Им предложили 3 контрольные работы. За каждую контрольную ставилась одна из оценок: 2, 3, 4 или 5. Верно ли, что найдутся два школьника, получившие одинаковые оценки на всех контрольных?

29. В квадрат со стороной 1 м бросили произвольным способом 51 точку. Докажите, что какие-то три из них можно накрыть квадратиком со стороной 0,2 м.

30. В квадрат со стороной 1 м бросили произвольным способом 51 точку. Докажите, что какие-то три из них можно накрыть кругом радиуса 71 м.

31. На квадратном столе со стороной 70 см лежит 100 квадратных салфеток со стороной 10 см. Докажите, что в стол можно вбить гвоздь, который проткнет не менее трех салфеток.

32. На плоскости даны 7 прямых, никакие две из них не параллельны. Докажите, что найдутся две прямые, угол между которыми  меньше 26° .

33. В сфере радиуса 1 летают 9 мух. Верно ли, что в любой момент времени найдутся две из них, расстояние между которыми не превосходит 3?

34. На плоскости отмечено 5 точек с целочисленными координатами. Докажите, что середина по крайней мере одного из соединяющих их отрезков также имеет целочисленные координаты.

35. Кот Базилио пообещал Буратино открыть великую тайну, если он составит чудесный квадрат 6*6 из чисел +1, −1, 0 так, чтобы все суммы по строкам, по столбцам и по большим диагоналям были различны. Помогите Буратино.

36. В классе 25 человек. Известно, что среди любых трех из них есть двое друзей. Докажите, что есть ученик, у которого не менее 12 друзей.

37. На плоскости отмечена 101 точка, не все они лежат на одной прямой. Через каждую пару отмеченных точек красным карандашом проводится прямая. Докажите, что на плоскости существует точка, через которую проходит не менее 11 красных прямых.

38. На Земле океан занимает больше половины площади поверхности. Докажите, что в мировом океане можно указать две диаметрально противоположные точки.