Принцип Дирихле в олимпиадной математике: как узнать задачу и решить её
2 мин чтения2 просмотра
Принцип Дирихле — одна из первых идей, которую встречают на школьном этапе ВсОШ, и одна из тех,
что остаются полезными до заключительного. Формулировка простая: если раскладывать n + 1 предмет по n ящикам,
то хотя бы в одном ящике окажется не меньше двух предметов.
Как узнать задачу на Дирихле
- В условии есть слова «докажите, что найдутся два…», «обязательно ли…», «какое наименьшее число нужно взять, чтобы наверняка…».
- Объектов заметно больше, чем возможных «вариантов» (остатков, цветов, клеток, дней).
- Ответ — не конкретный пример, а гарантия существования.
Алгоритм
- Решите, что будет «кроликами» (объекты), а что — «клетками» (признак, по которому их сравниваем).
- Посчитайте клетки. Если кроликов больше — принцип срабатывает.
- Сформулируйте вывод: в одной клетке два объекта, значит у них совпадает признак, — и из этого выведите нужное.
Пример
Среди любых 6 целых чисел найдутся два, разность которых делится на 5.
Клетки — остатки от деления на 5: их ровно пять (0, 1, 2, 3, 4). Чисел шесть, значит два числа имеют одинаковый остаток,
и их разность делится на 5.
Обобщённый вариант
Если kn + 1 предмет разложен по n ящикам, то в каком-то ящике не меньше k + 1 предмета. Этой формой решаются задачи
вида «в классе 40 учеников — докажите, что хотя бы четверо родились в одном месяце» (40 > 3 · 12).
Типичные ошибки
- Клетки выбраны так, что их больше, чем объектов, — принцип ничего не даёт. Ищите более «грубый» признак.
- В «наименьшем числе» забывают пример, показывающий, что на единицу меньше не хватит. Без примера оценка неполная.
- Решение пишут без явного указания, что именно является клетками. Проверяющий снимет баллы за обоснование.
Есть вопрос по задаче или теме — пишите в наш Telegram, разберём.
Частые вопросы
Для каких классов эта работа?
5–11 классы.
Ответы
Ответов пока нет. Будьте первым, кто ответит.