Урок 3. Принцип Дирихле: кроликов больше, чем клеток

Олимпиадная математика · ~40 минут

Если 10 кроликов рассадить по 9 клеткам, то в какой-то клетке окажется хотя бы два кролика. Очевидно? Абсолютно. Но эта детская банальность — один из самых мощных инструментов олимпиадной математики. Весь фокус в том, чтобы придумать, кто тут «кролики» и кто «клетки».

🎯 Что ты узнаешь

• Точную формулировку принципа Дирихле и обобщённый вариант
• Как выбирать «клетки», чтобы задача решилась
• Геометрический Дирихле — точки внутри фигуры
• Приложения к делимости

📖 Разбираемся в теме

Простой принцип

📌 Запомни: Если $n$ предметов разложены по $k$ ящикам и $n > k$, то хотя бы в одном ящике лежит не меньше двух предметов.

Доказательство «от противного» в одну строку: если бы в каждом ящике было $\le 1$ предмета, всего было бы $\le k$ предметов, но их $n > k$. Противоречие.

Обобщённый принцип

Что, если предметов сильно больше ящиков?

📌 Запомни: Если $n$ предметов разложены по $k$ ящикам, то в каком-то ящике лежит не меньше $\lceil n/k \rceil$ предметов (потолок — округление вверх).

Почему: если бы в каждом ящике было $\le \lceil n/k\rceil - 1$ предметов, всего было бы не больше $k\cdot(\lceil n/k\rceil - 1) < n$ — проверь, что это действительно меньше $n$. Значит, где-то предметов не меньше $\lceil n/k\rceil$.

💡 Аналогично есть «зеркальный» принцип: в каком-то ящике не больше $\lfloor n/k\rfloor$ предметов (пол — округление вниз). Оба варианта полезны: один даёт оценку «хотя бы столько-то», другой «не больше чем».

Как придумать клетки

Это главная трудность. Клетки почти никогда не даны в условии — их надо изобрести. Частые идеи:

• остатки от деления (клетки = возможные остатки);
• части фигуры (клетки = кусочки, на которые разбита область);
• пары/суммы/разности значений.

🤔 А знаешь ли ты? Принцип назван в честь Дирихле (XIX век), но по-английски он называется pigeonhole principle — «принцип голубятни»: голуби садятся в ячейки голубятни. Кролики и голуби — одна и та же идея.

Геометрический Дирихле

Если фигуру площади (или длины, объёма) $S$ разбить на $k$ частей и внутри разместить $n$ точек с $n>k$, то в какую-то часть попадёт $\ge 2$ точки. Значит, между ними расстояние не больше диаметра части.

⚠️ Тонкость: точки на границе двух частей надо заранее договориться относить к одной из частей, иначе «одна точка в двух клетках».

✍️ Разбор задачи

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

Решение. Клетки — это остатки от деления на 5: их ровно пять — $0,1,2,3,4$. Каждое из шести чисел попадает в клетку по своему остатку. Кроликов 6, клеток 5, $6>5$ — по принципу Дирихле два числа $a$ и $b$ попадут в одну клетку, то есть дадут одинаковый остаток при делении на 5. Тогда $a-b$ делится на 5 (разность чисел с равными остатками кратна модулю). ∎

Задача (геометрия). В квадрат со стороной 1 бросили 5 точек. Докажи, что какие-то две из них находятся на расстоянии не больше $\frac{\sqrt2}{2}$.

Решение. Разобьём квадрат $1\times 1$ на 4 маленьких квадрата со стороной $\tfrac12$ (клетки). Точек 5, квадратиков 4, значит в какой-то квадратик попадут хотя бы две точки. Расстояние между двумя точками одного квадратика не превосходит его диагонали $\frac{\sqrt2}{2}$ (диагональ квадрата со стороной $\tfrac12$ равна $\tfrac12\cdot\sqrt2$). Значит, эти две точки на расстоянии $\le \frac{\sqrt2}{2}$. ∎

📝 Задачи

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

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

3. В коробке лежат носки: 10 красных, 10 синих и 10 зелёных, вперемешку и в темноте. Сколько носков надо вытащить, чтобы гарантированно получить пару одного цвета? А чтобы гарантированно получить синюю пару?

4. Докажи, что среди любых 52 целых чисел найдутся два, у которых либо сумма, либо разность делится на 100.

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

6. Дано 100 целых чисел. Докажи, что из них можно выбрать несколько (хотя бы одно), сумма которых делится на 100. (Подсказка: рассмотри частичные суммы $a_1$, $a_1+a_2$, $\dots$ и их остатки.)

7. Каждую точку плоскости покрасили в один из двух цветов. Докажи, что найдутся две точки одного цвета на расстоянии ровно 1. (Подсказка: рассмотри вершины подходящего равностороннего треугольника или более хитрой фигуры.)

8. ⭐ Из чисел $1, 2, 3, \dots, 200$ выбрали 101 число. Докажи, что среди выбранных обязательно найдутся два, одно из которых делится на другое. (Подсказка: каждое число запиши как $2^k\cdot m$ с нечётным $m$; чем могут быть «клетки»?)