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

Математика · ~55 минут

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

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

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

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

Главная идея

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

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

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

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

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

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

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

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

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

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

Усиленный принцип Дирихле

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

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

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

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

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

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

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

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

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

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

Как рассуждаем. Что взять за ящики? Месяцев ровно 12 — отличный кандидат, их мало. Что за предметы? Ученики — их 13, это больше. Раскладываем учеников по «ящикам-месяцам» (каждого в тот месяц, в котором он родился). Предметов (13) больше, чем ящиков (12). По принципу Дирихле найдётся месяц, в который попало не меньше двух учеников. Это и значит, что двое родились в один месяц.

Ответ: доказано (ящики — 12 месяцев, учеников 13 > 12).

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

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

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

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

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

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

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

(Бонус: тут даже работает усиленный принцип. Жителей больше, чем 2·500 001 = 1 000 002? Не обязательно, но в любом случае двое точно найдутся.)

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

Пример 4. В квадрате со стороной 2 поставили 5 точек. Докажи, что найдутся две точки на расстоянии не больше √2 друг от друга.

Как рассуждаем. Тут ящиков с виду нет вообще — есть просто квадрат. Весь фокус в том, чтобы сделать ящики самому, разрезав квадрат. Разобьём квадрат 2×2 на 4 одинаковых квадратика 1×1 (как окно на 4 части). Это наши 4 ящика.

Точек 5, ящиков 4. Предметов больше — по принципу Дирихле в каком-то квадратике 1×1 окажется не меньше двух точек.

Теперь вопрос: насколько далеко могут быть две точки внутри одного квадратика 1×1? Самое большое расстояние внутри квадрата — это его диагональ. Диагональ квадрата со стороной 1 равна √(1²+1²) = √2. Значит, две точки в одном квадратике не дальше, чем √2 друг от друга.

Ответ: доказано (4 квадратика 1×1, 5 точек, две попадут в один, а там расстояние ≤ √2).

Пример 5. Из чисел 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 чисел — какая-то пара набралась целиком).

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

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

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

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

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

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

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

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

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

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

• Обычный принцип: предметов больше ящиков ⟹ где-то ≥ 2 предмета.
• Усиленный: предметов больше k·N ⟹ где-то ≥ k+1 предмет.
• Принцип доказывает, что что-то существует, но не говорит, где именно.
• Частые «ящики»: дни/месяцы, цвета, остатки, пары чисел, кусочки фигуры, число знакомых.
• Если не получается — попробуй разбить объект (квадрат, отрезок, множество чисел) на удобные группы.

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

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