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

Принципом Дирихле традиционно называют следующее утверждение:

если в 4 клетках сидит хотя бы 5 кроликов, то по крайней мере в одной клетке находится хотя бы 2 кролика.

В общем виде принцип Дирихле выглядит так:

Пусть есть хотя бы n·k+1 объект, которые распределены в n множествах. Тогда хотя бы в одном множестве находится хотя бы k+1 объект.

Докажем это утверждение методом от противного. Пусть в каждой клетке сидит не более k кроликов. Поскольку клеток n, то всего кроликов должно быть не более n·k, что противоречит условию.

Пример.

25 кроликов расположились в 12 клетках. Докажите, что хотя бы в 1 клетке хотя бы 3 кролика.

Следствие 1.

Если сумма n чисел равна S, то среди них есть число, не большее S/n и не меньшее S/n.

Следствие 2. (геометрический вариант принципа Дирихле)

Если на отрезке AB лежат несколько отрезков, сумма длин которых равна α·AB (α> 1), тогда какая-то точка принадлежит, по крайней мере, [α] + 1 отрезкам.

Задачи для самостоятельного решения:

1. Шесть школьников съели 7 конфет. Докажите, что хотя бы один школьник съел хотя бы 2 конфеты.
2. 13 школьников съели 30 конфет. Докажите, что хотя бы 1 школьник съел хотя бы 3 конфеты.
3. В классе 15 учеников. Докажите, что найдутся хотя бы 2 ученика, родившихся в одном месяце.
4. В классе 25 учеников. Докажите, что найдутся хотя бы 3 ученика, родившихся в одном месяце.
5. Какое наименьшее число учеников должно быть в школе, имеющей 30 классов, для того, чтобы в ней обязательно был класс, в котором не меньше 28 учеников?
6. В квадрате 8×8 закрашено 33 клетки. Докажите, что три какие-то закрашенные клетки образуют уголок из трех клеток.
7. В классе 30 человек. Паша сделал 13 ошибок, а остальные меньше. Докажите, что какие-то три ученика сделали одинаковое количество ошибок.
8. Докажите, что среди любых шести целых чисел найдутся два, разность которых кратна 5.
9. 100 человек сидят за круглым столом, причем более половины из них — мужчины. Докажите, что какие-то двое мужчин сидят друг напротив друга.
10. Докажите, что на шахматной доске нельзя расставить более 8 ладей так, чтобы никакие две из них не били друг друга.
11. Докажите, что в любой компании есть два человека, имеющих одинаковое число знакомых в этой компании.
12. Имеется 101 пуговица одного из 11 цветов. Докажите, что либо среди этих пуговиц найдутся 11 пуговиц одного цвета, либо 11 пуговиц разных цветов. 
13. Дано восемь различных натуральных чисел, не превосходящих 15. Докажите, что среди их положительных попарных разностей есть три одинаковых.
14. Докажите, что из любых пяти натуральных чисел можно выбрать три числа, сумма которых делится на 3.
15. Докажите, что из любых семи натуральных чисел можно выбрать три числа, сумма которых делится на 3. 
16. 15 белок собрали 100 орехов. Докажите, что какие-то две из них собрали одинаковое количество орехов.
17. В бригаде 7 человек; их суммарный возраст — 332 года. Докажите, что из них можно выбрать троих человек, сумма возрастов которых не менее 142 лет.
18. Грани куба окрашены в 2 цвета. Докажите, что найдутся две соседние одноцветные грани.
19. Докажите, что никакая прямая не может пересекать все три стороны треугольника.
20. Имеется 25 конфет 3 сортов. Верно ли, что не менее 9 из них будут какого-то одного сорта?
21. Внутри равностороннего треугольника со стороной 1 расположено 5 точек. Доказать, что расстояние между некоторыми двумя из них меньше 0,5.
22. В прямоугольнике 5×6 закрашено 19 клеток. Докажите,что в нем можно выбрать квадрат 2×2 , в котором закрашено не менее трех клеток.
23. Докажите, что из любых двенадцати натуральных чисел можно выбрать два, разность которых делится на 11.
24. Можно ли в клетках квадратной таблицы 5×5 расставить числа 0, +1, –1 так, чтобы все суммы в каждом столбце, в каждой строке и на каждой из двух диагоналей были различны?
25. В ряд выписано пять натуральных чисел: a₁, a₂, a₃, a₄, a₅. Докажите, что либо одно из них делится на 5, либо сумма нескольких рядом стоящих чисел делится на 5.
26. Несколько дуг окружности покрашены в красный цвет. Сумма длин окрашенных дуг меньше половины длины окружности. Докажите, что существует диаметр, оба конца которого не окрашены.
27. В квадрате со стороной 1 отметили 51 точку. Докажите, что три из них можно покрыть кругом диаметра 1/7.
28. В квадрате со стороной 1 расположено несколько окружностей с суммой их длин, равной 10. Докажите, что существует прямая, параллельная сторонам квадрата, которая пересекает не менее четырех окружностей.
29. Докажите, что любой выпуклый многоугольник с четным числом сторон имеет диагональ, которая не параллельна ни одной из сторон многоугольника.
30. Доказать, что для всякого простого числа p, не равного 2 или 5, существует натуральное число k такое, что p·k записывается в десятичной системе одними единицами.
31. В правильном двадцатиугольнике отметили 9 вершин. Докажите, что найдется равнобедренный треугольник с вершинами в отмеченных точках.
32. Узлы бесконечной клетчатой бумаги раскрашены в два цвета. Докажите, что существуют две вертикальные и две горизонтальные прямые, на пересечении которых лежат
    точки одного цвета.