Принцип Дирихле в олимпиадной математике: как узнать задачу и решить её

2 мин чтения2 просмотра

Принцип Дирихле — одна из первых идей, которую встречают на школьном этапе ВсОШ, и одна из тех,
что остаются полезными до заключительного. Формулировка простая: если раскладывать n + 1 предмет по n ящикам,
то хотя бы в одном ящике окажется не меньше двух предметов.

Как узнать задачу на Дирихле

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

Алгоритм

  1. Решите, что будет «кроликами» (объекты), а что — «клетками» (признак, по которому их сравниваем).
  2. Посчитайте клетки. Если кроликов больше — принцип срабатывает.
  3. Сформулируйте вывод: в одной клетке два объекта, значит у них совпадает признак, — и из этого выведите нужное.

Пример

Среди любых 6 целых чисел найдутся два, разность которых делится на 5.
Клетки — остатки от деления на 5: их ровно пять (0, 1, 2, 3, 4). Чисел шесть, значит два числа имеют одинаковый остаток,
и их разность делится на 5.

Обобщённый вариант

Если kn + 1 предмет разложен по n ящикам, то в каком-то ящике не меньше k + 1 предмета. Этой формой решаются задачи
вида «в классе 40 учеников — докажите, что хотя бы четверо родились в одном месяце» (40 > 3 · 12).

Типичные ошибки

  • Клетки выбраны так, что их больше, чем объектов, — принцип ничего не даёт. Ищите более «грубый» признак.
  • В «наименьшем числе» забывают пример, показывающий, что на единицу меньше не хватит. Без примера оценка неполная.
  • Решение пишут без явного указания, что именно является клетками. Проверяющий снимет баллы за обоснование.

Есть вопрос по задаче или теме — пишите в наш Telegram, разберём.

Частые вопросы

Для каких классов эта работа?

5–11 классы.

Ответы

Ответов пока нет. Будьте первым, кто ответит.

Ответы и разборы — в Telegram