Принцип Дирихле: задачи с решением и разбор идеи

Принцип Дирихле - один из самых коротких и при этом самых мощных приёмов комбинаторики: если предметов больше, чем ящиков, то хотя бы в одном ящике лежит больше одного предмета. Утверждение звучит почти как банальность, но именно на нём строятся десятки олимпиадных задач, где напрямую посчитать ничего нельзя. Сложность всегда в одном месте - правильно назначить «зайцев» и «клетки». Ниже разберём формулировку, усиленную версию через целую часть и несколько типовых задач с решением. Если хотите сразу прогнать свою задачу по шагам, соберите условие в форме под этим абзацем.

Формулировка принципа Дирихле

Базовая формулировка: если $n$ предметов разложены по $k$ ящикам и $n > k$, то найдётся ящик, в котором лежит не меньше двух предметов. Предметы традиционно называют «зайцами», ящики - «клетками», поэтому принцип ещё зовут принципом ящиков или принципом клеток и зайцев.

Доказательство занимает одну строку и идёт от противного: пусть в каждой клетке не более одного зайца. Тогда всего зайцев не больше $k$, что противоречит условию $n > k$. Значит, хотя бы в одной клетке зайцев минимум два.

Несмотря на тривиальность, идея работает там, где прямой подсчёт невозможен: мы не указываем конкретную клетку с перегрузом, а лишь доказываем, что такая клетка обязана существовать. Это типичный неконструктивный аргумент.

Рассчитать для своей задачи

Усиленный принцип: формула с целой частью

Когда зайцев намного больше, чем клеток, важна не просто «двойка», а точная нижняя оценка перегруза. Усиленная формулировка: если $n$ зайцев сидят в $k$ клетках, то найдётся клетка, в которой не меньше

$$\left\lceil \frac{n}{k} \right\rceil$$

зайцев, где $\lceil x \rceil$ - округление вверх. Эквивалентно: найдётся клетка хотя бы с $\lfloor (n-1)/k \rfloor + 1$ зайцами.

Доказательство снова от противного: если в каждой из $k$ клеток меньше $\lceil n/k \rceil$ зайцев, то есть не больше $\lceil n/k \rceil - 1$, то суммарно зайцев не больше $k\left(\lceil n/k \rceil - 1\right) < n$ - противоречие. Симметрично работает и оценка снизу: какая-то клетка содержит не больше $\lfloor n/k \rfloor$ зайцев.

Главная трудность: что считать клетками

Сам принцип элементарен - вся работа в моделировании. Решая задачу, всегда отвечайте на два вопроса: что взять за зайцев и что за клетки. Удачный выбор клеток превращает задачу в одну строчку, неудачный делает её нерешаемой.

Несколько рабочих идей для клеток:

• Остатки от деления. Если важна делимость на $m$, берите $m$ клеток - по остатку $0, 1, \dots, m-1$.
• Геометрические области. Разбейте фигуру на части (квадраты, секторы, полоски) - это клетки, а точки внутри - зайцы.
• Значения функции или суммы. Частичные суммы, разности, цвета, координаты по модулю - всё это потенциальные клетки.

Назначив клетки, проверьте неравенство $n > k$ (или $n > (m-1)k$ для усиленной версии) - и принцип сработает автоматически.

Рассчитать для своей задачи

Задача 1: совпадение остатков

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

Решение. Клетки - остатки от деления на $11$, их ровно $11$: это $0, 1, \dots, 10$. Зайцы - наши $12$ чисел; каждое попадает в клетку по своему остатку. Так как $12 > 11$, по принципу Дирихле какие-то два числа $a$ и $b$ попали в одну клетку, то есть дают одинаковый остаток. Тогда их разность $a - b$ делится на $11$, что и требовалось.

Здесь видно ядро метода: мы не ищем эти два числа явно, а лишь доказываем, что они обязаны существовать.

Задача 2: точки в равностороннем треугольнике

Условие. Внутри равностороннего треугольника со стороной $1$ отмечены $5$ точек. Докажите, что какие-то две из них находятся на расстоянии меньше $\tfrac{1}{2}$.

Решение. Разобьём треугольник средними линиями на $4$ маленьких равносторонних треугольника со стороной $\tfrac{1}{2}$ - это клетки. Зайцы - $5$ точек. Так как $5 > 4$, в один маленький треугольник попали хотя бы две точки. Но расстояние между любыми двумя точками внутри треугольника со стороной $\tfrac{1}{2}$ строго меньше $\tfrac{1}{2}$ (диаметр такого треугольника равен длине стороны и достигается только на вершинах). Значит, найденная пара точек ближе, чем $\tfrac{1}{2}$.

Задача 3: усиленная версия в действии

Условие. В классе $30$ учеников. Докажите, что хотя бы трое из них родились в один и тот же месяц.

Решение. Клетки - $12$ месяцев, зайцы - $30$ учеников. По усиленному принципу найдётся месяц, в котором не меньше

$$\left\lceil \frac{30}{12} \right\rceil = \lceil 2{,}5 \rceil = 3$$

учеников. Значит, как минимум трое родились в одном месяце. Проверка через «противное»: если бы в каждом месяце было не больше двух, всего учеников было бы не больше $12 \cdot 2 = 24 < 30$ - противоречие.

Это типичная схема: подобрали число клеток так, чтобы $(m-1)k < n$, и усиленный принцип сразу выдал нужную кратность $m$.

Принцип Дирихле и непрерывный случай

У принципа есть «непрерывный» аналог: если конечную величину (длину, площадь, массу) разложить по нескольким частям и средняя доля известна, то найдётся часть не меньше средней и часть не больше средней. Формально: если сумма $k$ чисел равна $S$, то хотя бы одно из них $\geq S/k$ и хотя бы одно $\leq S/k$.

Эта версия закрывает задачи вида «докажите, что какой-то угол не больше $60^\circ$» или «какая-то полоска покрыта не более чем наполовину». Логика та же: среднее существует всегда, значит кто-то лежит не выше и кто-то не ниже среднего.

Не путайте, кстати, принцип Дирихле с одноимённым признаком Дирихле для рядов - это разные результаты, объединённые только фамилией математика: первый про комбинаторику, второй про сходимость знакопеременных рядов.

Частые ошибки

• Перепутаны зайцы и клетки. Если по ошибке взять клетками то, чего больше, неравенство $n > k$ не выполнится и принцип «не сработает». Всегда: клеток должно быть меньше, чем зайцев.
• Слишком много клеток. Берёте $k$ настолько большим, что $n \leq k$ - тогда гарантии нет вовсе. Клетки нужно укрупнять, а не дробить.
• Забыли усиленную версию. Когда требуется «хотя бы трое», базовый принцип даёт только «хотя бы двое». Нужна формула с $\lceil n/k \rceil$.
• Нестрогие неравенства в геометрии. Точка на границе клетки или совпадение на отрезке могут испортить строгое «меньше». Уточняйте, открыта область или замкнута.
• Попытка указать конкретную клетку. Принцип неконструктивен: он доказывает существование перегруза, но не говорит, в какой именно клетке. Искать «ту самую» клетку не нужно.

FAQ

Чем базовый принцип Дирихле отличается от усиленного? Базовый гарантирует, что при $n > k$ хотя бы в одной клетке окажется минимум два зайца. Усиленный даёт точную нижнюю оценку: найдётся клетка не меньше чем с $\lceil n/k \rceil$ зайцами. Базовый - частный случай усиленного при небольшом перегрузе.

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

Можно ли с помощью принципа найти конкретные объекты? Нет, принцип неконструктивен: он доказывает, что нужная пара или клетка существует, но не указывает её. Для явного поиска нужны другие методы - перебор, алгоритм, конструкция.

Коротко

Принцип Дирихле утверждает: если зайцев больше, чем клеток, то в какой-то клетке их минимум два, а усиленная версия даёт оценку $\lceil n/k \rceil$. Всё мастерство - в выборе зайцев и клеток: чаще всего клетками служат остатки от деления, геометрические области или значения функции. Доказательство всегда идёт от противного и неконструктивно: мы гарантируем существование перегруза, не указывая конкретную клетку. Отработав три типовые схемы - совпадение остатков, разбиение фигуры и усиленную кратность, - вы закроете большинство школьных и олимпиадных задач на эту тему.