Урок 3. Принцип Дирихле (принцип ящиков)

Математика

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

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

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

Спорим на мороженое? В Москве точно живут два человека с абсолютно одинаковым числом волос на голове. Не «примерно одинаковым», а волосок в волосок. Я не считал ничьи волосы и не знаю этих людей в лицо, но я уверен на все сто. Как такое можно знать заранее? Есть один смешной до простоты принцип, который позволяет доказывать существование вещей, не находя их. Знакомься: принцип Дирихле.

Главная идея

Представь: у тебя 3 клетки (ящика) и 4 голубя. Если все голуби сядут по клеткам, то хотя бы в одной клетке окажется не меньше двух голубей. Почему? Если бы в каждой клетке сидело не больше одного голубя, всего голубей было бы максимум 3. А их 4. Противоречие!

Это и есть принцип Дирихле (его ещё называют «принцип ящиков» или «принцип голубей и клеток»):

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

Точная формулировка: если в $N$ ящиков разложили больше $N$ предметов, то найдётся ящик, где хотя бы 2 предмета.

Звучит как очевидность, и это правда очевидность. Но фокус в том, что в реальных задачах «ящики» и «предметы» спрятаны, и их надо разглядеть. В этом и весь талант.

Рис. 1. Голубей 4, ящиков 3: куда-то сели двое сразу

Как это доказывают (от противного)

Принцип Дирихле всегда доказывается от противного, и важно понимать этот ход. Предположим обратное: пусть в КАЖДОМ ящике не больше одного предмета. Тогда всего предметов не больше, чем ящиков. Но по условию предметов больше, чем ящиков. Противоречие! Значит, наше предположение неверно, и какой-то ящик переполнен.

Запомни схему рассуждения, она пригодится во всех задачах:

Назвать ящики (групп должно быть мало).
Назвать предметы (их должно быть много, больше, чем ящиков).
Сказать: предметов больше ящиков, значит, два предмета попали в один ящик.
Объяснить, что «два в одном ящике» означает то, что требуется в задаче.

💡 Лайфхак: 90% сложности любой задачи на Дирихле — это придумать, что считать ящиками, а что предметами. Само правило срабатывает за одну строчку. Поэтому, увидев слова «обязательно найдутся», «хотя бы двое», «гарантированно», сразу спрашивай себя: «А что тут ящики? Чего тут много?»

Где искать «ящики»: копилка приёмов

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

Календарь. Месяцы (12), дни года (365 или 366), дни недели (7), часы (24). Если людей/событий больше, двое совпадут.
Цвета и виды. Носки, карандаши, шары, масти карт. Ящик — цвет, предмет — вытащенная вещь.
Остатки от деления. При делении на $n$ бывает ровно $n$ остатков: $0, 1, 2, \dots, n - 1$ . Это готовые $n$ ящиков для задач на делимость (об этом чуть ниже: там целый отдельный трюк).
Пары чисел. Разбить множество чисел на пары с нужным свойством (сумма, разность). Каждая пара — ящик.
Кусочки фигуры. Разрезать квадрат, треугольник, отрезок на маленькие части. Каждая часть — ящик, точки внутри — предметы.
Числовые характеристики. Число волос, рост в миллиметрах, число друзей, число рукопожатий — всё, что принимает ограниченный набор значений.

🤔 Как понять, чего должно быть мало? Ящиков должно быть строго меньше, чем предметов. Значит, ящики — это «то, чего в задаче конечное, заранее известное количество» (12 месяцев, 7 цветов, 6 остатков), а предметы — «то, чего в задаче как бы много или больше» (люди, вытащенные носки, выбранные числа). Если запутался, прикинь два числа и посмотри, какое больше. Меньшее число — ящики.

Усиленный (обобщённый) принцип Дирихле

А что, если предметов гораздо больше, чем ящиков? Тогда в каком-то ящике будет не просто 2, а ещё больше.

📌 Запомни: Если в $N$ ящиков положили больше, чем $k \cdot N$ предметов, то найдётся ящик, где не меньше $k + 1$ предмета.

Проверь логику тем же «от противного»: если бы в каждом из $N$ ящиков было максимум $k$ предметов, всего было бы максимум $k \cdot N$ . А у нас больше. Значит, где-то набралось хотя бы $k + 1$ .

Например: 25 учеников, 3 варианта оценки за тест (3, 4, 5). Ящиков 3. Так как $25 > 8 \cdot 3 = 24$ , то найдётся оценка, которую получили хотя бы 9 человек ( $k = 8$ , $k + 1 = 9$ ).

Есть удобный способ прикинуть «сколько же точно наберётся». Если раскладываешь $P$ предметов по $N$ ящикам, то в самом полном ящике всегда не меньше, чем $P$ делить на $N$ и округлить вверх. Например, $100$ писем в $9$ ящиков: $100 : 9 \approx 11, 1$ , округляем вверх, значит, в каком-то ящике не меньше 12 писем.

⚠️ Осторожно с округлением! Округлять надо именно вверх, а не «как обычно». $100 : 9 = 11, 1$ : если бы везде было по 11, вышло бы всего $99 < 100$ , одно письмо не поместилось. Значит, где-то точно 12. Никогда не округляй такие оценки вниз — это самая частая ошибка в задачах на усиленный Дирихле.

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

Иногда «ящиков» в задаче не видно: есть просто фигура, внутри которой разбросаны точки. Как тут применить Дирихле? Хитрость в том, что ящики можно сделать самим: разрезать фигуру на маленькие кусочки. Каждый кусочек станет ящиком, а точки — «зайцами».

📌 Запомни: Если фигуру разрезали на $N$ частей и поставили внутри больше $N$ точек, то в какую-то одну часть попадут хотя бы две точки.

Зачем это нужно? Затем, что две точки, попавшие в один маленький кусочек, не могут быть далеко друг от друга: их расстояние не больше размера кусочка. Так «в одном ящике две точки» превращается в «какие-то две точки близко».

Разберём на классической задаче.

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

Рассуждаем по шагам:

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

Для квадрата со стороной $a$ диагональ по теореме Пифагора равна $a^{2} + a^{2} = a 2$ . У нашего квадратика $a = \frac{1}{2}$ , поэтому диагональ $= \frac{1}{2} 2 = \frac{2}{2}$ . Значит, две точки в одном квадратике не могут отойти дальше $\frac{2}{2}$ , что и требовалось доказать.

Рис. 2. Дальше диагонали две точки в квадрате не разойдутся

Главная хитрость таких задач — правильно нарезать фигуру: кусочков должно быть на один меньше, чем точек (чтобы сработал Дирихле), и при этом каждый кусочек — достаточно маленьким, чтобы поймать нужную близость.

Принцип Дирихле и делимость: магия остатков

Это самое красивое применение. Вспомни: когда мы делим целое число на $n$ , остаток бывает только один из набора $0, 1, 2, \dots, n - 1$ , всего ровно $n$ вариантов. Вот эти $n$ остатков и есть готовые ящики!

Ключевая мысль, из-за которой всё работает:

📌 Следствие о делимости: Разность двух чисел, дающих одинаковый остаток при делении на $n$ , всегда делится на $n$ без остатка.

Почему это так? Докажем математически. Пусть числа $a$ и $b$ при делении на $n$ дают один и тот же остаток $r$ . По определению деления с остатком это значит, что их можно записать так:

a = k_{1} n + r, b = k_{2} n + r,

где $k_{1}$ и $k_{2}$ — целые числа (сколько раз $n$ «уместилось» в числе), а $r$ — их общий остаток. Вычтем одно из другого:

a - b = (k_{1} n + r) - (k_{2} n + r) = k_{1} n - k_{2} n = (k_{1} - k_{2}) n .

Справа стоит $n$ , умноженное на целое число $(k_{1} - k_{2})$ , а значит, разность $a - b$ делится на $n$ . Что и требовалось доказать. (Верно и наоборот: если разность делится на $n$ , то остатки обязаны совпасть.)

Отсюда рабочий рецепт для задач вида «докажи, что найдутся два числа, разность которых делится на $n$ »:

Ящики — это $n$ возможных остатков при делении на $n$ .
Предметы — выбранные числа. Каждое кладём в ящик по его остатку.
Если чисел больше $n$ , два попадут в один ящик: у них одинаковый остаток.
Значит, их разность делится на $n$ . Готово!

💡 Лайфхак: Слова «разность делится на $n$ », «сумма делится на $n$ », «два числа сравнимы» — почти всегда сигнал: ящики это остатки при делении на $n$ . Их ровно $n$ штук.

Аналогия из жизни

Если в школе учатся 367 детей, то обязательно есть двое с одинаковым днём рождения. Ящиков — 366 (все возможные даты, включая 29 февраля). Детей — 367, это больше. Значит, две даты совпадут. Заметь: мы не знаем, КТО эти двое и КАКОЙ это день, но точно знаем, что они есть. Принцип Дирихле почти всегда доказывает «существование», не указывая пальцем.

🤔 А знаешь ли ты? Тот самый спор про волосы из начала урока решается этим же приёмом. У человека на голове максимум около 150 000 волос, значит, «ящиков» (вариантов числа волос) меньше миллиона. А жителей крупного города — миллионы. Предметов больше ящиков: двое с одинаковым числом волос обязаны существовать. Принцип назван в честь немецкого математика Петера Густава Лежёна Дирихле, жившего в XIX веке. По-немецки его называли «Schubfachprinzip» — «принцип выдвижных ящиков», как ящики в комоде.

✍️ Разбор примеров

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

⏱ Попробуй сам прямо сейчас: чего в этой задаче ровно 12 штук? Это и будут ящики. Потом читай дальше.

Как рассуждаем. Ящики — это 12 месяцев, предметы — 25 учеников (каждого кладём в тот месяц, в котором он родился). Здесь работает усиленный принцип Дирихле. Пойдём от противного: предположим, что в каждом месяце родилось не больше двух учеников. Тогда всего учеников было бы не больше $12 \cdot 2 = 24$ . Но в классе их 25, а $25 > 24$ — противоречие! Значит, предположение неверно, и в какой-то месяц попало не меньше трёх учеников.

Короче: по усиленному принципу в каком-то месяце будет не меньше $⌈ \frac{25}{12} ⌉ = 3$ учеников.

Ответ: доказано (12 месяцев, 25 учеников; если бы всюду было по ≤ 2, вышло бы ≤ 24 < 25).

Пример 2. В тёмной комнате в ящике лежат носки двух цветов — чёрные и белые — вперемешку. Сколько носков нужно вытащить вслепую, чтобы среди них точно нашлась пара одного цвета?

Как рассуждаем. Здесь ящики — это цвета (их 2: чёрный и белый), а предметы — вытащенные носки. Чтобы гарантированно получить два носка одного цвета, нам нужно, чтобы предметов было больше, чем ящиков, то есть больше 2. Значит, 3 носка хватит: при трёх носках и двух цветах какие-то два обязательно одного цвета.

Проверим, что двух мало: можно вытащить один чёрный и один белый. Пары нет. А три уже гарантируют.

Ответ: 3 носка.

💡 Правило хитрого гардероба: Чтобы гарантированно набрать пару при $c$ цветах, надо вытащить $c + 1$ носок. Проверь: 2 цвета → 3 носка (как выше), 4 цвета → 5 носков. Логика всегда одна: «один плохой случай на каждый ящик, плюс ещё один сверху, чтобы сломать невезение».

Пример 3. В большом городе живёт больше 1 000 000 человек. Известно, что у любого человека на голове не больше 500 000 волос. Докажи, что есть двое жителей с одинаковым числом волос.

Как рассуждаем. Ящики — возможные количества волос: от 0 до 500 000. Сколько таких чисел? От 0 до 500 000 включительно — это 500 001 значение. Предметы — жители, их больше 1 000 000.

Жителей (>1 000 000) намного больше, чем ящиков (500 001). По обычному принципу Дирихле уже найдутся двое с одинаковым числом волос.

(Бонус: тут даже работает усиленный принцип. Жителей больше, чем $2 \cdot 500001 = 1000002$ ? Не обязательно, но в любом случае двое точно найдутся.)

⚠️ Не забудь про ноль! Возможных чисел волос не 500 000, а 500 001, потому что лысина (0 волос) тоже вариант. Когда считаешь ящики-числа «от 0 до $M$ », их всегда $M + 1$ , а не $M$ . Промах на единицу здесь ничего не портит (жителей всё равно больше), но в других задачах такая ошибка может всё сломать.

Ответ: доказано (ящиков-«чисел волос» 500 001, жителей больше миллиона).

Пример 4. Из чисел 1, 2, 3, …, 10 выбрали любые 6 штук. Докажи, что среди выбранных найдутся два числа, дающие в сумме 11.

Как рассуждаем. Снова ящиков не видно: надо их изобрести. Раз речь про сумму 11, разобьём все числа от 1 до 10 на пары, дающие в сумме 11: (1, 10), (2, 9), (3, 8), (4, 7), (5, 6).

Получилось 5 пар — это наши 5 ящиков. Каждое из чисел 1…10 лежит ровно в одном ящике. Мы выбрали 6 чисел. Раскладываем эти 6 выбранных чисел по 5 ящикам-парам. Предметов (6) больше, чем ящиков (5), значит, в какой-то ящик попали оба числа из пары. А оба числа пары дают в сумме как раз 11.

Ответ: доказано (5 пар с суммой 11, выбрали 6 чисел, и какая-то пара набралась целиком).

Пример 5. Из чисел 1, 2, 3, …, 100 выбрали любые 7 разных. Докажи, что среди них найдутся два числа, разность которых делится на 6.

⏱ Попробуй сам: на что делят, чтобы получить ящики? На 6. А сколько бывает остатков при делении на 6?

Как рассуждаем. Это классическая задача «на остатки» — самый красивый вид Дирихле. При делении на 6 остаток бывает только один из шести: $0, 1, 2, 3, 4, 5$ . Вот наши 6 ящиков. Каждое выбранное число кладём в ящик по его остатку от деления на 6 (например, число 20 даёт остаток 2 и идёт в ящик «2»; число 27 даёт остаток 3 и идёт в ящик «3»).

Чисел выбрали 7, ящиков-остатков 6. Предметов больше: по принципу Дирихле два числа попали в один ящик, то есть дали одинаковый остаток. А два числа с одинаковым остатком отличаются на число, кратное 6: их разность делится на 6. Что и требовалось.

Маленькая проверка на пальцах: пусть выбрали 8 и 26. Остатки: $8 = 6 + 2$ (остаток 2), $26 = 24 + 2$ (остаток 2) — совпали. Разность $26 - 8 = 18 = 6 \cdot 3$ — делится на 6.

Ответ: доказано (6 остатков при делении на 6, чисел 7 > 6, два дают одинаковый остаток → их разность кратна 6).

Пример 6. В коробке лежит по 100 шаров четырёх цветов. Не глядя, вытащили 25 шаров. Докажи, что среди них не меньше 7 шаров одного цвета.

Как рассуждаем. Тут пахнет усиленным принципом: нам мало «двух одинаковых», нужно сразу «не меньше 7». Ящиков 4 (цвета), предметов 25 (вытащенные шары).

Прикинем через деление: $25 : 4 = 6, 25$ , округляем вверх, получаем 7. Значит, в каком-то цвете не меньше 7 шаров.

Проверим строго через усиленный принцип. Хотим показать: где-то $\geq 7$ , то есть $k + 1 = 7$ , отсюда $k = 6$ . Условие усиленного принципа: предметов должно быть больше $k \cdot N = 6 \cdot 4 = 24$ . У нас 25, и правда $25 > 24$ . Значит, найдётся цвет с не менее чем 7 шарами.

А почему нельзя обойтись шестью? Если бы каждого цвета было максимум по 6, всего шаров было бы максимум $6 \cdot 4 = 24 < 25$ . Один шар «лишний», и он делает какой-то цвет седьмым.

Ответ: доказано ( $25 > 6 \cdot 4$ , значит, где-то не меньше 7 шаров одного цвета).

Пример 7. В компании из 6 человек докажи, что обязательно найдутся либо трое попарно знакомых, либо трое попарно незнакомых.

Как рассуждаем. Это посложнее, но идея с Дирихле тут стартовая. Возьмём одного человека, назовём его Аня. У Ани есть 5 остальных, и с каждым из них она либо знакома, либо нет. Раскладываем этих 5 человек по 2 ящикам: «знакомые с Аней» и «незнакомые с Аней».

5 человек, 2 ящика: по принципу Дирихле в каком-то ящике не меньше 3 человек (ведь $5 > 2 \cdot 2 = 4$ , усиленный принцип даёт $\geq 3$ ). Пусть для определённости трое знакомы с Аней (если бы трое были незнакомы, рассуждение зеркальное). Назовём их Б, В, Г.

Теперь смотрим на эту тройку Б, В, Г.

Если хоть какие-то двое из них знакомы между собой (например, Б и В), то Аня, Б, В попарно знакомы (Аня знакома и с Б, и с В по выбору, а Б с В знакомы). Вот тройка знакомых!
Если же никакие двое из Б, В, Г не знакомы между собой, значит, Б, В, Г попарно незнакомы. Вот тройка незнакомых!

В любом случае нужная тройка нашлась.

🤔 А знаешь ли ты? Этот пример — кусочек целой науки под названием «теория Рамсея». Её главная мысль: в любом достаточно большом беспорядке обязательно прячется порядок. Сколько людей ни собери в компанию, в ней неизбежно образуется аккуратная тройка знакомых или незнакомых: хаоса «без всякой структуры» просто не существует.

Ответ: доказано (выделяем 3 человек одного «типа отношений» с одним, и среди них замыкается нужная тройка).

💡 Запомни главное

Главная работа — придумать ящики (их мало) и предметы (их больше, чем ящиков). Дальше принцип Дирихле делает вывод за тебя.

Обычный принцип: предметов больше ящиков ⟹ где-то $\geq 2$ предмета.
Усиленный: предметов больше $k \cdot N$ ⟹ где-то $\geq k + 1$ предмет. При делении округляй вверх.
Геометрический: разрежь фигуру на кусочки, и кусочки станут ящиками, а близость точек внутри одного кусочка ограничена его диагональю.
Делимость: остатков при делении на $n$ ровно $n$ штук — это готовые ящики. Одинаковый остаток ⟺ разность делится на $n$ .
Принцип доказывает, что что-то существует, но не говорит, где именно.
Частые «ящики»: дни/месяцы, цвета, остатки, пары чисел, кусочки фигуры, число знакомых.
Если не получается, попробуй разбить объект (квадрат, отрезок, множество чисел) на удобные группы.

📝 Домашнее задание

В коробке лежат карандаши 4 цветов. Сколько карандашей нужно вытащить вслепую, чтобы среди них наверняка оказалось два одного цвета?
В классе 25 учеников. Докажи, что хотя бы трое из них родились в один месяц.
В коробке лежат носки трёх цветов. Сколько носков нужно вытащить вслепую, чтобы гарантированно получить пару одного цвета? А чтобы гарантированно получить пару чёрного цвета, если чёрных всего 5, а остальных по 20?
Выбрали 9 разных целых чисел. Докажи, что среди них найдутся два, разность которых делится на 8.
В равностороннем треугольнике со стороной 2 отметили 5 точек. Докажи, что какие-то две из них на расстоянии не больше 1.
На шахматной доске 8×8 расставили 9 ладей. Докажи, что какие-то две из них стоят в одной строке (горизонтали).
Из чисел 1, 2, …, 100 выбрали 51 число. Докажи, что среди них найдутся два соседних (отличающихся на 1).
⭐ На вечеринке собрались n человек (n ≥ 2), некоторые пожимали друг другу руки. Докажи, что обязательно найдутся двое, сделавшие одинаковое число рукопожатий. (Подсказка: сколько рукопожатий может сделать один человек — от 0 до скольких? Почему числа 0 и n−1 не могут встретиться одновременно?)