Принцип кроликов и клеток
Если в $N$ клетках сидят не менее $N + 1$ кроликов, то в какой-то из клеток сидит не менее 2-х кроликов.
Данное утверждение носит называние ‘‘принцип Дирихле’’. Доказывается методом от противного: если бы в каждой клетке сидело не более одного кролика, то в N клетках сидело бы не более $N$ кроликов – противоречие.
Более общая формулировка принципа:
Если в $n$ коробок положить $k$ предметов и $k > n$, то существует хотя бы одна коробка, в которой находится не менее 2-х предметов.
Обобщённый принцип Дирихле
Если $pn + 1$ предметов поместить в n коробок, то хотя бы одна из них будет содержать $p + 1$ предметов.
Задачи
Задача 1
В лесу растёт 1 млн ёлок и известно, что на каждой из них не более 600 тыс иголок. Доказать, что в лесу найдутся хотя бы две ёлки с одинаковым количеством иголок.
- 1 000 000 ёлок (предметов)
- 600 001 ящиков - на каждой из ёлок $0 \leqslant k \leqslant 600 000$ иголок
- Т.к. предметов больше, чем ящиков, то в каком-то ящике находится более одного предмета.
Задача 2
Доказать, что среди 6-ти целых чисел найдутся два числа, разность которых делится на 5.
- 5 коробок: { 0, 1, 2, 3, 4, 5 } - остатки от деления на 5,
- Если распределить числа по коробкам, то в одной коробке окажется два числа,
- Следовательно, существует как минимум два числа с одинаковым остатком от деления на 5,
- Тогда разность этих чисел делится на 5.
Задача 3
Доказать, что для любого $n \in \mathbb{N}$, $n \geqslant 1$ существует $k \in \mathbb{N}$, состоящее только из чисел 0 и 5, такое, что оно делится на $n$.
- $a_1 = 50, a_2 = 5050, a_n = \underbrace{5050..50}$ ($n$ раз)
- Распределим эти предметы по коробкам $s_i \in {0, 1, …, n-1}$
- В коробку $s_i$ помещаем число $a_k$ если оно имеет остаток от деления равный $i$
- Если в $s_0$ находится 1 предмет - то задача решена.
- Иначе, $n - 1$ коробке находится $n$ предметов, следовательно существует два числа, имеющих одинаковы остаток от деления на $n$
- Т.к. разность двух чисел, состоящих их 5 и 0 тоже состоит из 5 и 0, то разность этих двух чисел и есть ответ.
Задача 4
В доме 40 человек. Существует ли такой месяц, когда хотя бы 4 ученика празднует свои дни рождения?
- Коробки - месяцы (12 шт)
- Предметы - люди (40 = 12 * 3 + 4)
- Существует коробка по крайней мере с 3 + 1 предметами
Sources
- Генкин С.А., Итенберг И.В., Фомин Д.В. Ленинградские математические кружки, 1994.
- Pigeonhole Principle, http://bars-minsk.narod.ru/teachers/dirichle.html