Dirichlet's Box Principle - 13 Oct 2009
Sergey Sobolev
Если 11 кроликов посажены в 10 клеток, то в какой-то клетке
находятся по крайней мере два кролика. Действительно,
предположив противное (в каждой клетке находится не более
одного кролика), мы получим, что кроликов не более 10, --
противоречие с условием.
Принцип Дирихле (Pigeonhole Principle, Dirichlet's Box
Principle) в формулировке с кроликами и клетками:
Если в n клетках сидит n+1 кролик, то найдётся по
крайней мере одна клетка, в которой сидят не менее
двух кроликов.
В задачах "на принцип Дирихле" стоит понять, что играет роль
кроликов, а что -- роль клеток.
1. Докажите, что если 21 кролик или больше посажены в 10
клеток, то в какой-то клетке находится по крайней мере 3
кролика.
2. В классе учится 25 учеников. Докажите, что найдутся 2
ученика, родившиеся в одном и том же месяце. Обязательно ли
найдутся 3 таких ученика?
3. Из чисел 1, 2, ... , 49, 50 выбрали 26 чисел. Обязательно ли
среди них найдутся два числа, отличающиеся друг от друга на 1?
Подсказка. Поделим эти 50 чисел на 25 "клеток":
| 1, 2 | 3, 4 | ... | 49, 50 |
4. Докажите, что из любых 11 натуральных чисел можно выбрать 2
числа, разность которых делится на 10.
5. Докажите, что из любого 21 натурального числа можно выбрать
3 таких, разности которых делятся на 10.
6. Докажите, что из любых 10 натуральных чисел, ни одно из
которых не делится на 10, можно выбрать такие 2 числа, разность
которых делится на 10.
Подсказка. Чисел 10 (это кролики), а возможных последних цифр
(это клетки) только 9, так как цифра 0 исключается условием
задачи.
7. Докажите, что из любых 10 натуральных чисел можно выбрать
несколько (возможно, одно), сумма которых делится на 10.
Подсказка. Пусть a_1, a_2, ..., a_{10} -- эти 10 чисел.
Рассмотрим 10 сумм
b_1=a_1, b_2=a_1+a_2, ..., b_{10}=a_1+a_2+...+a_{10}.
Если какое-то из чисел b_1, b_2, ..., b_{10} делится на 10, то
нужная выборка есть. Если же ни одно из них не делится на 10,
применим к ним задачу 6.
8. 15 ребят собрали 100 орехов. Докажите, что какие-то 2 из них
собрали одинаковое число орехов.
9. Можно ли накрыть равносторонний треугольник двумя меньшими
равносторонними треугольниками?
Подсказка. Допустим, что так накрыть можно. Вершин 3, а
накрывающих треугольников 2, какие-то 2 вершины будут...
10. В равносторонний треугольник со стороной 1 бросили 5 точек.
Докажите, что среди них найдутся две точки, расстояние между
которыми не превышает 1/2.
Подсказка. Разрежьте этот треугольник на 4 равносторонних
треугольника.
11. В квадрат со стороной 4 бросили 5 точек. Докажите, что
найдутся две точки, расстояние между которыми меньше 3.
Подсказка. Измерения показывают, что в квадрате со стороной 2
диагональ меньше 3 (этот факт можно и доказать).
12. В квадрат со стороной 2 бросили 10 точек. Докажите, что
найдутся две точки, расстояние между которыми меньше 1.
Подсказка. В квадрате со стороной 2/3 диагональ меньше 1.
13. Докажите, что в квадратную коробочку со стороной 3 нельзя
положить 10 монет диаметра 1 без наложений.
Подсказка. Допустим, что можно. Центры монет находятся в
квадрате со стороной 2 (нарисуйте его на дне коробочки).
Примените предыдущую задачу.
14. Докажите, что в данный момент на Земле живут два человека,
которые родились в одну секунду.
Замечание. Задачи 4-7 --- задачи про свойства целых чисел
..., -2, -1, 0, 1, 2, ...,
можно рассмотреть варианты и обобщения этих задач.
Натуральные числа (1, 2, 3,...) взяты для удобства говорить не
про остаток от деления числа на 10, а про последнюю цифру в его
десятичной записи.
Решения принимаются до 13 октября. На сайте кружка
http://mathcircle.csmath.org
на странице задания есть pdf-файл для печати.
Alpha (10-12 лет): задачи 1-5, 8-10, остальное по вкусу.
Beta (13-14 лет): все задачи.