Содержание
Что такое принцип Дирихле#
Принцип Дирихле помогает доказать, что повтор неизбежен. Если предметов больше, чем ящиков, то хотя бы в одном ящике окажется не меньше двух предметов. В олимпиадной задаче предметами обычно становятся числа, точки, ученики или выбранные объекты, а «ящиками» — группы, остатки, отрезки или области.
Главная трудность — не запомнить формулу, а правильно разбить объекты на группы. После этого доказательство часто занимает несколько строк. Принцип полезен в тренировочных задачах муниципального этапа ВсОШ по математике для 7–11 классов, особенно когда условие спрашивает, обязательно ли найдётся пара объектов с общим свойством.
Алгоритм решения#
1. Определите объекты, которые нужно распределить.
2. Выберите группы так, чтобы совпадение внутри группы давало нужный результат.
3. Посчитайте число объектов и групп.
4. Сравните числа: если объектов больше, чем групп, повтор существует.
5. Объясните, почему повтор действительно означает то, что требуется доказать.
Не начинайте с перебора всех вариантов, если объектов много. Сначала ищите ограниченное число возможных «ящиков»: например, остатки при делении, месяцы рождения, клетки сетки или интервалы.
Пример 1. Остатки при делении#
Докажем: среди любых шести целых чисел найдутся два, разность которых делится на 5.
При делении на 5 число имеет один из пяти остатков: 0, 1, 2, 3 или 4. Это пять групп. Шесть чисел распределены по пяти группам, поэтому два числа попадут в одну группу. У них одинаковый остаток при делении на 5, значит их разность делится на 5.
Здесь важно не утверждать, что сами числа обязательно делятся на 5. Совпадают именно остатки, поэтому на 5 делится разность.
Пример 2. Точки в квадрате#
В квадрат со стороной 2 помещены десять точек. Докажем, что найдутся две точки на расстоянии не больше √2.
Разделим квадрат на четыре квадрата со стороной 1. Это четыре группы, а точек десять. По принципу Дирихле в одном маленьком квадрате окажутся как минимум две точки. Самое большое расстояние внутри квадрата со стороной 1 — его диагональ, равная √(1²+1²)=√2. Значит, выбранная пара находится на расстоянии не больше √2.
Для такого доказательства не нужно знать точное расположение всех точек: достаточно ограничить максимальное расстояние внутри одной группы.
Как выбрать группы в задаче#
Если условие говорит о делимости разности, проверьте остатки по модулю. Если речь о повторе признака, посчитайте возможные значения этого признака. В геометрии удобно разбить область на одинаковые части и оценить наибольшее расстояние внутри одной части. В комбинаторной задаче полезно сначала спросить себя: сколько разных типов объектов вообще возможно?
Типичная ошибка — назвать число групп, но не связать совпадение с требуемым выводом. Например, совпавшие остатки дают делимость разности, а две точки в одной клетке позволяют оценить расстояние. Пишите эту связь явно.
Проверьте себя#
Докажите, что среди любых девяти целых чисел найдутся два, разность которых делится на 8.
При делении на 8 возможны восемь остатков. Девять чисел распределяются по восьми группам, поэтому два имеют одинаковый остаток. Их разность делится на 8.
Как готовиться к задачам на доказательство#
После решения выпишите отдельно объекты, группы и число групп. Затем проговорите, какое свойство даёт попадание двух объектов в одну группу. Если объяснение работает только для выбранного примера, но не для всех объектов из условия, доказательство ещё не завершено. В тренировочных вариантах ВсОШ используйте этот способ как один из инструментов, а не как готовый ответ к любой задаче на перебор.
Материал предназначен для подготовки. Примеры в черновике составлены редакцией и не являются заданиями или ответами официального этапа ВсОШ.
