§ 2. Принцип Дирихле

Определения и обозначения

В задачах о принципе Дирихле объекты распределяют по группам, которые называют ящиками. Например, ученики — объекты, а месяцы их рождения — 12 ящиков: каждый ученик попадает в ящик своего месяца. Ящики не обязательно настоящие коробки: ими могут быть категории, числа или возможные остатки. Такое представление помогает заменить непривычную задачу простой задачей о распределении.

Основной принцип Дирихле формулируется так: если объектов больше, чем ящиков, то хотя бы в одном ящике окажется не менее двух объектов. Например, если 13 предметов распределить по 12 ящикам, нельзя положить в каждый ящик не более одного предмета: для всех предметов не хватит отдельных ящиков. Это правило позволяет доказывать, что совпадение обязательно есть, даже если неизвестно, где именно оно возникнет.

Обобщённый принцип Дирихле говорит: если N объектов распределены по k ящикам, найдётся ящик как минимум с ⌈N/k⌉ объектами. Здесь N — общее число объектов, а k — число ящиков, включая те, в которых может ничего не оказаться. Знак ⌈ ⌉ означает округление вверх до ближайшего целого числа: например, ⌈13/5⌉ = 3. Обобщение нужно, когда объектов больше не просто на один, а настолько, что можно гарантировать несколько объектов в одной группе.

При выборе групп необходимо проверить, что каждый объект можно отнести к одному из ящиков по ясному правилу. Ящиком может быть, например, один из возможных остатков при делении числа на 12. Тогда числа с одинаковым остатком попадают в один ящик, а различие между остатками не требуется знать заранее. Такой выбор помогает связать распределение с нужным в задаче свойством.

Как это устроено

Представим 13 объектов и 12 ящиков. Если бы в каждом ящике лежал не более чем один объект, то занятыми могли бы оказаться не более 12 ящиков, а объектов поместилось бы не больше 12. Но объектов 13, поэтому предположение о том, что в каждом ящике не более одного, невозможно. Значит, хотя бы один ящик содержит два объекта или больше.

Обобщённую формулировку можно объяснить от противного. Пусть в каждом из k ящиков меньше ⌈N/k⌉ объектов; поскольку число объектов целое, в каждом будет не больше ⌈N/k⌉ − 1. Тогда всего объектов окажется не больше k · (⌈N/k⌉ − 1), а это число меньше N. Получается противоречие: по условию объектов N, поэтому хотя бы в одном ящике должно быть не менее ⌈N/k⌉ объектов.

Чтобы распознать объекты и ящики, спроси себя: что дано в задаче и по какому признаку это можно разделить на ограниченное число групп? В задаче о днях рождения объектами будут ученики, а ящиками — месяцы. В задаче о числах часто удобно разбить их на группы по остатку от деления. Ящики выбирают так, чтобы они охватывали все объекты, а попадание нескольких объектов в одну группу помогало получить требуемый вывод.

Принцип применяют, когда нужно доказать существование совпадений, делимости или пары с заданным свойством. Если два числа имеют одинаковый остаток при делении на 12, их разность делится на 12; если два предмета попали в одну группу, у них совпал признак, по которому создали эту группу. Поэтому после выбора ящиков важно отдельно объяснить, почему объекты из одного ящика дают нужное свойство. Сам подсчёт гарантирует, что такие объекты найдутся.

Принцип сообщает, что нужный ящик или пара существуют, но обычно не указывает, где именно они находятся. Это происходит потому, что подсчёт рассматривает все возможные распределения, а не прослеживает судьбу каждого объекта. Если задача требует назвать конкретные объекты, одного принципа может быть недостаточно. Зато для доказательства, что совпадение неизбежно, такого общего вывода часто хватает.

Формулировки принципа Дирихле

Сначала найди общее число объектов и возможных ящиков, затем выбери подходящую строку таблицы. Для последней строки отдельно проверь, что каждый объект учтён и что попадание в один ящик действительно даёт нужный вывод. Если это не так, нужно изменить способ группировки.

Разбор задач

Ученики и месяцы рождения

Условие. В классе 13 учеников. Докажите, что как минимум у двух учеников день рождения приходится на один месяц. Нужно найти не конкретные имена, а доказать неизбежность совпадения по месяцу. Для этого сгруппируем учеников по месяцу рождения.

1. Объекты — 13 учеников, ящики — 12 месяцев года.
2. Поскольку 13 больше 12, по основному принципу Дирихле хотя бы в одном месяце окажутся не менее двух учеников.
3. Все ученики распределены по этим 12 ящикам, поэтому вывод относится к кому-то из учеников класса.

Ответ. Как минимум у двух учеников день рождения приходится на один месяц. Принцип не сообщает, какой это месяц, и для доказательства это не требуется.

Разность чисел делится на 12

Условие. Даны 13 целых чисел. Докажите, что найдутся два числа, разность которых делится на 12. Здесь полезно искать признак, который принимает ограниченное число значений. Таким признаком будет остаток при делении на 12.

1. Объекты — 13 данных чисел, ящики — 12 возможных остатков: от 0 до 11.
2. По основному принципу два числа попадут в один ящик, то есть будут иметь одинаковый остаток при делении на 12.
3. Если числа представить как 12a + r и 12b + r, их разность равна 12(a − b) и делится на 12.

Ответ. Среди данных чисел обязательно есть два, разность которых делится на 12. Решение работает и тогда, когда среди чисел есть отрицательные: у любого целого числа остаток при делении на 12 один из 12 возможных.

Пара чисел с суммой 11

Условие. Из чисел от 1 до 10 выбрали 6 различных чисел. Докажите, что среди выбранных есть два числа, сумма которых равна 11. Разобьём все десять чисел на группы так, чтобы числа внутри каждой группы в сумме давали 11. Здесь ящиками служат пары чисел.

1. Составим пять пар: (1, 10), (2, 9), (3, 8), (4, 7), (5, 6).
2. Выбранные числа распределяются по этим пяти парам; в каждой паре может быть выбрано не более двух чисел.
3. Если бы из каждой пары выбрали не более одного числа, всего выбрали бы не более пяти чисел. Но выбрано шесть, значит, обе части какой-то пары выбраны.

Ответ. Среди шести чисел есть пара с суммой 11. Например, доказательство гарантирует существование такой пары, но не определяет, какая именно из пяти пар оказалась выбранной целиком.

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

Ошибка: считать ящиками только группы, которые уже оказались заняты. Это может уменьшить их число и привести к неверному применению принципа; в задаче о месяцах учитывают все 12 месяцев, даже если в некоторые никто не родился. Ошибку допускают, когда считают лишь наблюдаемые случаи, а не все возможные группы. Проверь себя: каждый объект должен попадать в один из заранее определённых ящиков.

Ошибка: утверждать, что принцип указывает конкретный ящик или конкретную пару. Он доказывает существование, но не обязательно позволяет назвать объекты; так происходит потому, что в рассуждении используются только количества. Проверь вывод: если он обещает назвать месяц или пару, должно быть дополнительное рассуждение, а не один только принцип.

Ошибка: округлять N/k вниз в обобщённом принципе. Например, 13/5 = 2,6, но гарантированное число объектов в одном из пяти ящиков равно ⌈2,6⌉ = 3, а не 2. Округление вниз не даёт искомого минимального числа, потому что сумма объектов может оказаться больше N. Проверь себя на примере 13 объектов и 5 ящиков.

Ошибка: не доказывать, что распределение охватывает все объекты и что общий ящик даёт требуемое свойство. Можно верно посчитать ящики, но забыть, что несколько чисел с одинаковым остатком дают разность, делящуюся на делитель. Это упускают, когда после подсчёта сразу объявляют результат. Проверь два условия: каждый объект попал в ящик, а совпадение в ящике ведёт к нужному выводу.

Связь с другими темами

Для применения принципа нужны навыки группировки предметов по признаку, подсчёта групп и сравнения чисел. Эти действия помогают заметить, что разные на вид задачи можно свести к одному распределению. Особенно часто ящиками становятся возможные остатки при делении, поэтому принцип связан с делимостью и теорией чисел. Он также встречается в комбинаторике — разделе математики, изучающем способы выбора и расположения объектов, — и в задачах на совпадения и доказательство существования.

Что запомнить

• Объектами и ящиками могут быть не только предметы и коробки, но и числа, остатки или группы по признаку.
• Если объектов больше, чем ящиков, хотя бы в одном ящике окажется не менее двух объектов.
• Для N объектов и k ящиков найдётся ящик как минимум с ⌈N/k⌉ объектами.
• Сначала нужно правильно выбрать объекты и ящики.
• Принцип доказывает существование, но не обязательно указывает конкретный пример.
• Для задач на остатки ящиками часто служат возможные остатки при делении.