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

Принцип Дирихле (Pigeonhole Principle, Dirichlet's Box Principle) в формулировке с кроликами и клетками:

Если в n клетках сидит n+1 кролик, то найдётся по крайней мере одна клетка, в которой сидят не менее двух кроликов.

1. Докажите, что если 21 кролик или больше посажены в 10 клеток, то в какой-то клетке находится по крайней мере 3 кролика.

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

3. Из чисел 1, 2, ... , 49, 50 выбрали 26 чисел. Обязательно ли среди них найдутся два числа, отличающиеся друг от друга на 1?

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

Подсказка. Чисел 11 (это кролики), а возможных последних цифр (это клетки) только 10.

5. Докажите, что из любого 21 натурального числа можно выбрать 3 таких, разности которых делятся на 10.

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

7. Докажите, что из любых 10 натуральных чисел можно выбрать несколько (возможно, одно), сумма которых делится на 10.

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

9. Можно ли накрыть равносторонний треугольник двумя меньшими равносторонними треугольниками?

10. В равносторонний треугольник со стороной 1 бросили 5 точек. Докажите, что среди них найдутся две точки, расстояние между которыми не превышает 1/2.

11. В квадрат со стороной 4 бросили 5 точек. Докажите, что найдутся две точки, расстояние между которыми меньше 3.

Подсказка. Измерения показывают (и можно доказать), что в квадрате со стороной 2 диагональ меньше 3.

12. В квадрат со стороной 2 бросили 10 точек. Докажите, что найдутся две точки, расстояние между которыми меньше 1.

13. Докажите, что в квадратную коробочку со стороной 3 нельзя положить 10 монет диаметра 1 без наложений.

Подсказка. Допустим, что можно. Заметьте, что центры монет находятся в квадрате со стороной 2 и примените предыдущую задачу.

14. Докажите, что в данный момент на Земле живут два человека, которые родились в одну секунду.

Alpha (10–12 лет): задачи 1–5, 8–10, остальное по вкусу.

Beta (13–14 лет): все задачи.