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

Идея метода: если $n+1$ предмет раскладывают по $n$ ящикам, то хотя бы в одном ящике окажется не менее двух предметов. Это очевидно — но именно эту очевидность принцип Дирихле (он же принцип «ящиков», pigeonhole principle) и эксплуатирует.

Метод состоит в том, что мы конструируем «ящики» (классы, группы) и «предметы» (объекты из условия) так, чтобы количество предметов заведомо превышало количество ящиков. Тогда в каком-то ящике окажется несколько предметов, и именно это «столкновение» даёт нам нужный вывод.

Жизненная аналогия: в любой группе из 367 человек найдутся двое с одинаковым днём рождения (так как дней в году не более 366). Это не надо доказывать сложными рассуждениями — достаточно сравнить 367 > 366.

Ключ к применению принципа — правильно выбрать «ящики»: слишком мелкие не дадут вывода, слишком крупные не докажут нужного. Часто ящики задаются остатками по модулю, геометрическими фигурами или числовыми интервалами.

• Простой принцип Дирихле: если $n+1$ предмет разложить по $n$ ящикам, то в каком-то ящике $\geq 2$ предмета. Условие: предметов строго больше, чем ящиков. Когда использовать: чтобы доказать существование двух объектов с одинаковым свойством.

• Усиленный принцип Дирихле: если $kn+1$ предметов разложить по $n$ ящикам, то в каком-то ящике $\geq k+1$ предметов. Когда использовать: когда нужно найти не просто пару, а группу из $k+1$ одинаковых.

• Непрерывный вариант (принцип Дирихле для отрезков): если $n+1$ точек расположены на отрезке длины $L$, то среди них найдутся две на расстоянии $\leq \frac{L}{n}$. Когда использовать: геометрические задачи на близость точек.

• Разбить множество по остаткам: в задачах о числах часто «ящики» — это классы вычетов по модулю $m$ (например, $\{0,1\}, \{1,2\}, \ldots$ или пары $\{k, n-k\}$).
• Геометрическое разбиение: нарезать квадрат (отрезок, треугольник) на $n$ частей и разместить $n+1$ точек — гарантируем попадание двух в одну часть.
• Разбить по сумме/разности: для $n+1$ различных чисел из $\{1,\ldots,2n\}$ разбить на пары $\{k, 2n+1-k\}$ — гарантируем пару с заданной суммой.
• Разбить по «дополнению»: числа, у которых одинаковый остаток по модулю $n$, образуют «ящик»; $n+1$ чисел — и один ящик заполнен.
• Подобрать правильное число ящиков: задать $n$ ящиков, убедиться что предметов $\geq n+1$, а затем показать, что два предмета в одном ящике дают нужное свойство.

Поверхностные признаки (что буквально написано):
- «Докажите, что среди $n$ чисел найдутся два...».
- «Среди любых $n$ точек найдутся две на расстоянии не более...».
- «Докажите, что найдётся подмножество с суммой, кратной $k$».

Структурные признаки (форма выражения, объекты):
- Количество объектов явно превышает количество «естественных» категорий (остатков, интервалов, пар).
- Задача говорит «среди любых $N$...» — это намёк на то, что $N$ специально подобрано больше числа ящиков.

Цель задачи (что от тебя хотят):
- Доказать существование (без нахождения конкретного примера).
- Найти минимальное $N$, при котором утверждение гарантировано.

Задача 1. Докажите, что среди любых 5 точек внутри (или на границе) квадрата со стороной 2 найдутся две точки на расстоянии не более $\sqrt{2}$.

Источник: классическая задача принципа Дирихле (ВсОШ школьный этап, геометрия)

Как думать (рассуждение ученика$):
1. $Что я вижу?* «Среди 5 точек найдутся две близкие» — классика Дирихле. Триггер: «среди любых $N$... найдутся два...».$2. *$Какой метод? Принцип Дирихле. Нужно придумать 4 «ящика» так, чтобы расстояние внутри каждого не превышало $\sqrt{2}$.$3. *$Первый ход: разобью квадрат со стороной 2 на 4 единичных квадрата (по 2×2 клетки$).
4. $Ключевая идея:* диагональ единичного квадрата = $\sqrt{2}$. 5 точек в 4 квадратах — два в одном, расстояние $\leq \sqrt{2}$.

Решение:
Разобьём квадрат $2\times 2$ на четыре единичных квадрата $1\times 1$ (четыре «ящика»). По принципу Дирихле, среди 5 точек найдутся две, попавшие в один и тот же единичный квадрат. Расстояние между любыми двумя точками единичного квадрата не превышает длины его диагонали $= \sqrt{1^2+1^2} = \sqrt{2}$. Утверждение доказано.

Ответ: утверждение доказано; оценка $\sqrt{2}$ достигается, например, при точках в четырёх углах квадрата $2\times 2$ и в его центре.

Что в этой задаче было главным: выбор «ящиков» (четыре единичных квадрата) был ключевым — их размер задаёт оценку расстояния.

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

Источник: тренировочная (классика принципа Дирихле, тип ВсОШ-7-9)

Как думать (рассуждение ученика$):
1. $Что я вижу?$ 11$ чисел, нужна делимость разности — значит, нужны одинаковые остатки по модулю $10.
2. $Метод*: принцип Дирихле. «Ящики» — остатки по модулю 10 (их 10 штук: 0, 1, ..., 9). Объектов $11 > 10.
3. $Первый ход: по принципу Дирихле два числа дадут одинаковый остаток.$4. *$Вывод: если $a \equiv b \pmod{10}$, то $10 \mid (a - b)$.

Решение:
Каждое из 11 целых чисел имеет остаток от деления на 10 — одно из значений $\{0, 1, 2, \ldots, 9\}$ (10 «ящиков»). По принципу Дирихле, среди 11 чисел найдутся два числа $a$ и $b$ с одинаковым остатком по модулю 10, то есть $a \equiv b \pmod{10}$, значит $10 \mid (a - b)$.

Ответ: утверждение доказано.

Что в этой задаче было главным: «ящики» — остатки по модулю 10 — мгновенно дают и конструкцию, и вывод.

• Ошибка: выбрать ящики неправильно — так, что объект может попасть в несколько ящиков сразу. → Почему неверно: принцип требует, чтобы разбиение было полным и попарно несовместным. → Как избежать: явно проверить: каждый объект попадает ровно в один ящик.

• Ошибка: перепутать, кто «ящики», а кто «предметы». → Например: в задаче про числа «ящики» — это остатки (их $n$), а «предметы» — числа (их $n+1$). → Как избежать: сформулировать явно: «предметов $P$ штук, ящиков $B$ штук, $P > B$».

• Ошибка: забыть доказать, что два объекта в одном ящике действительно дают нужное свойство. → Почему неверно: сам факт «два в одном ящике» ещё не является ответом — нужно показать, что из этого следует нужное. → Как избежать: явно написать «если $a$ и $b$ в одном ящике, то...».

• Ошибка: использовать принцип только в «одну сторону»: «найдутся два», не убедившись, что ящики исчерпывают все объекты. → Как избежать: убедиться, что каждый объект попадает хотя бы в один ящик.