Короткий ответ. Если объектов больше, чем ящиков, хотя бы в одном ящике окажутся минимум два объекта. В задаче важно назвать объекты и ящики, а затем проверить неравенство.
Принципом Дирихле называют утверждение о распределении объектов по ящикам. Если n объектов разложить по m ящикам и n больше m, то хотя бы один ящик содержит не меньше двух объектов.
Что нужно увидеть в условии
В одном и том же условии объектами могут быть ученики, числа или точки, а ящиками — месяцы, остатки или области рисунка. Решение начинается не с формулы, а с точного выбора этой пары. Затем сравнивают число объектов с числом ящиков.
Разбор на примере
В классе 31 ученик. Месяцев рождения 12, поэтому ученики — объекты, месяцы — ящики. 31>12, значит, как минимум два ученика родились в одном месяце. Мы не обязаны знать, в каком именно: принцип доказывает существование.
Ещё один пример
Выбрали 13 целых чисел. Остатков при делении на 12 всего 12: от 0 до 11. Два числа имеют одинаковый остаток, поэтому их разность делится на 12.
Алгоритм решения
Спросите себя: что должно совпасть или оказаться вместе? Это подсказывает ящики. Посчитайте их. После этого сопоставьте число объектов с числом ящиков и сформулируйте вывод словами задачи, а не только символом n>m.
Как проверить ответ
Проверка: в задаче про 13 чисел и остатки деление на 12 создаёт ровно 12 ящиков. Если бы чисел было 12, принцип не позволял бы гарантировать одинаковый остаток: все остатки могли бы встретиться по одному разу.
Почему этот приём работает
Обобщённая формулировка нужна, когда вопрос звучит не «найдутся ли два», а «сколько точно окажется вместе». Если 50 объектов распределяют по 8 ящикам, среднее равно 6,25. Из этого нельзя заключить, что в каждом ящике по семь объектов, но можно заключить: хотя бы в одном ящике не меньше семи. Иначе во всех было бы максимум по шесть, то есть всего не больше 48. Такой ход часто называют доказательством от противного.
Где обычно ошибаются
Нельзя выбирать ящики по внешнему сходству. В задаче об остатках ящики — не сами числа, а классы одинаковых остатков. Также неверно требовать назвать конкретную пару: это неконструктивное доказательство существования.
Проверьте себя
Попробуйте доказать: среди 11 целых чисел найдутся два, разность которых делится на 10. Сначала выберите десять ящиков-остатков, а затем примените принцип.
Почему принцип носит имя Дирихле
Название связано с математиком Петером Густавом Леженом Дирихле, который применял этот приём в теории чисел в XIX веке. Но сама идея встречалась и раньше: поэтому точнее говорить о принципе, названном в его честь, а не о том, что до него никто не замечал совпадений. Приём позволяет доказать существование нужной пары без перебора всех пар.
Как получить точную нижнюю границу
Для n объектов и m ящиков, где n и m — положительные целые числа, хотя бы в одном ящике будет не меньше ⌈n/m⌉ объектов. Скобки ⌈ ⌉ означают округление вверх. Для 31 ученика и 12 месяцев это 3, а не только 2: при максимум двух учениках на месяц поместились бы лишь 24 человека.
Граница достижима: 31 объект можно распределить по 12 ящикам так, чтобы в семи было по 3, а в пяти — по 2. Получается 7·3+5·2=31, и ни в одном нет четырёх. Значит, гарантировать четыре по одним этим данным нельзя.
Где это нужно вне олимпиады
В программировании принцип объясняет, почему короткие коды могут совпадать. Пусть каждому из 101 файла присвоили код из двух десятичных цифр, от 00 до 99. Кодов только 100, поэтому как минимум два файла получат одинаковый код. Это модель коллизии: одинаковый короткий код не доказывает, что сами файлы одинаковы. Как бы ни был устроен алгоритм присваивания, ограничение на число кодов остаётся.
Задача с рисунком: пять точек в квадрате
В квадрате со стороной 1 отмечены пять точек. Докажем, что две из них находятся на расстоянии не больше √2/2. Разделим квадрат на четыре квадрата со стороной 1/2. Каждую точку на разделительной линии заранее отнесём ровно к одной соседней части. Пять точек распределены по четырём частям: в одной окажутся две. Расстояние между ними не больше диагонали маленького квадрата, то есть √((1/2)²+(1/2)²)=√2/2.
Ответы к самопроверке
Почему среди 11 целых чисел найдутся два с разностью, кратной 10?
Остатков при делении на 10 ровно десять: 0, 1, …, 9. Если a=10q+r и b=10s+r, то a−b=10(q−s). Разность делится на 10, даже если сами числа отрицательны.
Сколько человек гарантируют троих с одним месяцем рождения?
25. Без троих в одном месяце каждый из 12 месяцев допускает максимум двух: 24 человека. Двадцать пятый нарушит это ограничение.
В темноте берут носки трёх цветов. Сколько носков нужно взять, чтобы гарантировать пару одного цвета?
Четыре. Цвета служат тремя ящиками. Первые три носка могут оказаться разных цветов; четвёртый обязательно совпадёт по цвету хотя бы с одним из них. Это гарантия цвета, а не размера или принадлежности готовой фабричной паре.
В отличие от парадокса дня рождения, здесь нет расчёта вероятности и предположения о случайности распределения. Вывод верен при любом допустимом распределении объектов.
Связанные темы
Сравните гарантированное совпадение с парадоксом дня рождения: в нём совпадение дней рождения оценивают вероятностно. Это другой вопрос, чем «обязательно ли найдётся совпадение при любом распределении».
Частый вопрос
Условие n>m достаточно, но не необходимо для совпадения. При n≤m совпадение возможно, однако не гарантировано. Например, три предмета можно разложить по трём ящикам по одному.
От ящиков к новым олимпиадным задачам
Не только узнать ответ, но и научиться искать идею. Посмотрите программу интерактивного курса по основам олимпиадной математики и выберите следующий шаг.