Принцип Дирихле — один из первых олимпиадных приёмов, с которым встречается школьник: если предметов больше, чем ящиков, в каком-то ящике окажется больше одного предмета. Формулировка простая, а применение почти всегда требует придумать, что считать «ящиками», а что — «предметами». Ниже — четыре реальные олимпиадные задачи разного уровня, где это нужно сделать по-разному.
Сама идея в одной фразе
Если предметов больше, чем ящиков, хотя бы в одном ящике окажутся два предмета. Короткое доказательство: если бы в каждом ящике лежало не больше одного предмета, предметов было бы не больше, чем ящиков, — противоречие.
Есть и общая формулировка: если предметов разложить по ящикам, где — положительное целое число, хотя бы в одном ящике будет не меньше предметов. Знак означает округление вверх до целого: например, . Иначе в каждом ящике было бы меньше предметов, а во всех ящиках вместе — меньше . В задачах важно определить, какие объекты считать предметами и по каким группам-«ящикам» их распределить.
Задача 1: разность, кратная 2021
Верно ли, что среди любых 2022 целых чисел можно выбрать два, разность которых кратна 2021?
Показать решение ↓Скрыть решение ↑
Решение
Остаток от деления на 2021 принимает одно из 2021 значений: . Если взять 2022 целых числа, то по принципу Дирихле хотя бы два из них дают одинаковый остаток при делении на 2021 — это и есть 2022 «кролика» в 2021 «клетке». Разность двух чисел с одинаковым остатком делится на 2021.
Источник задачи: Олимпиада «Надежда энергетики», 2022 год, заключительный этап, 8 класс, вариант 17081, задача 3 — условие
Официальное решение — задача 3 на второй странице PDF. Объяснение выше следует официальному решению.
Задача 2: кинотеатр и два сеанса
В кинотеатре семь рядов по 10 мест каждый. Группа из 50 детей сходила на утренний сеанс, а потом на вечерний. Докажите, что найдутся двое детей, которые на утреннем сеансе сидели в одном ряду и на вечернем тоже сидели в одном ряду.
Показать решение ↓Скрыть решение ↑
Решение
На утреннем сеансе 50 детей распределены по 7 рядам. Поскольку , по принципу Дирихле хотя бы в одном ряду утром сидело не меньше детей.
Теперь посмотрим, где эти не менее 8 детей сидели вечером: у них снова всего 7 рядов на выбор, а детей не меньше 8. По принципу Дирихле хотя бы двое из этих детей вечером оказались в одном ряду. Эти двое и утром сидели в одном ряду — том самом, где их было не меньше 8, — и вечером тоже в одном.
Источник задачи: 71-я Московская математическая олимпиада, 2008 год, 8 класс, задача 2 — официальный сайт ММО, mmo.mccme.ru (МЦНМО)
Задача 3: разноцветные шарики
В ящике лежат сто разноцветных шариков: 28 красных, 20 зелёных, 13 жёлтых, 19 синих, 11 белых и 9 чёрных. Какое наименьшее число шариков надо вытащить, не заглядывая в ящик, чтобы среди них заведомо оказалось не менее 15 шариков одного цвета?
Показать решение ↓Скрыть решение ↑
Решение
Ищем худший случай: наибольшее число шариков, которое можно вытащить, так и не набрав 15 одного цвета. Для этого берём от каждого цвета не больше 14 штук (а если шариков этого цвета меньше — все):
75 шариков можно вытащить, не получив 15 одного цвета. Но следующий, 76-й шарик неизбежно создаст группу из 15 какого-то цвета: обойти лимит 14 сразу по всем цветам больше нельзя.
Источник задачи: Олимпиада «Ломоносов», заключительный этап, 9 марта 2015 года, 10–11 класс, вариант 151, задача 1 — официальный сайт олимпиады «Ломоносов», МГУ
Задача 4: диагонали 2017-угольника
В правильном 2017-угольнике провели все диагонали. Петя выбирает наугад какие-то диагоналей. При каком наименьшем среди выбранных диагоналей гарантированно найдутся две, имеющие одинаковую длину?
Показать решение ↓Скрыть решение ↑
Решение
Выберем одну вершину многоугольника. Из неё выходят диагоналей: соединения с самой вершиной и с двумя соседними вершинами не считаются.
Эти диагонали разбиваются на пары равной длины. В каждой паре концы диагоналей расположены симметрично относительно прямой, проходящей через выбранную вершину и центр многоугольника. Пар будет . У разных пар длины различаются: чем больше меньший центральный угол, на который опирается диагональ, тем длиннее соответствующая хорда. Так мы получили 1007 разных длин.
Любую диагональ многоугольника можно поворотом совместить с диагональю, выходящей из выбранной вершины. Значит, других длин нет. Теперь применим принцип Дирихле: «предметы» — выбранные диагонали, а 1007 «ящиков» — их возможные длины. Среди любых 1008 диагоналей две обязательно окажутся в одном «ящике», то есть будут равны по длине.
Осталось проверить, что меньшего числа недостаточно. Можно выбрать по одной диагонали из каждой пары у выбранной вершины — получатся 1007 диагоналей разных длин. Поэтому наименьшее равно 1008.
Источник задачи: архив РСОШ, 9 класс, вариант 3-а, задача 4 — ссылка на комплект в разделе «Заключительный этап» каталога Olimpiada.ru — условие и официальное решение. Это каталог, а не сайт организатора. Прямой PDF РСОШ на момент проверки недоступен; содержание сверено по полной индексированной копии
Курс по теме
Тематические курсы в записи
Тематические курсы в записи — отдельные занятия по приёмам вроде принципа Дирихле, инвариантов, комбинаторики и графов.
Частые вопросы
Принцип Дирихле — это теорема, которую нужно доказывать на олимпиаде?
В решении можно назвать принцип Дирихле и пояснить, какие объекты распределяются по каким группам и почему объектов достаточно для нужного вывода. Можно обойтись и без названия: предположить, что в каждой группе объектов меньше требуемого, и получить противоречие. Например, если в каждом из семи рядов не больше семи детей, всего детей не больше 49, а по условию их 50.
Как понять, что в задаче нужно применять именно Дирихле?
Частый признак — вопрос «докажите, что найдутся два одинаковых» или «докажите, что что-то обязательно произойдёт» при достаточно большом числе объектов. Но само по себе такое требование ещё не определяет метод: сначала попробуйте найти подходящее распределение по группам.
Можно ли применить принцип Дирихле несколько раз в одной задаче?
Да, задача 2 выше — ровно такой случай: сначала Дирихле находит ряд с восемью детьми утром, потом Дирихле применяется второй раз — уже к вечернему рассаживанию этих восьми.
С какого возраста имеет смысл разбирать такие задачи?
Задача 1 (про остатки) доступна уже в 7–8 классе — идея принципа Дирихле не требует знаний старше средней школы, нужна только уверенная работа с остатками от деления.
Источники
- «Надежда энергетики», 2022 год — официальные решения заключительного этапа для 8 класса — вариант 17081, задача 3
- energy-hope.ru — олимпиада «Надежда энергетики» — официальный архив заданий
- mmo.mccme.ru — Московская математическая олимпиада — официальный сайт ММО (МЦНМО)
- olympiads.msu.ru — олимпиада «Ломоносов» — официальный сайт МГУ
- Olimpiada.ru — каталог материалов олимпиады «Покори Воробьёвы горы!» — содержит ссылку на архив РСОШ. Прямой PDF сейчас недоступен, условие и решение проверены по полной индексированной копии.