Принцип Дирихле за 10 минут

Олимпиады · 10 мин · июнь 2026

Слышал про принцип Дирихле, но так и не понял, как его применять? Лови. Это один из самых частых приёмов олимпиадной математики — и при этом один из самых простых по идее. Через десять минут ты будешь узнавать его в задачах и решать как минимум на школьном и муниципальном туре. Договорились? Погнали.

Что это вообще такое — на пальцах

Представь: у тебя есть 10 зайцев и 9 клеток. Рассаживаешь зайцев по клеткам — как угодно, хоть всех в одну. Утверждение: хотя бы в одной клетке точно окажется не меньше двух зайцев. Почему? Если бы в каждой клетке сидело максимум по одному, всего поместилось бы максимум 9 зайцев. А у нас 10. Противоречие — значит, где-то набилось двое и больше.

Вот и весь принцип. По-научному его называют принципом Дирихле (а в англоязычных учебниках — pigeonhole principle, «принцип голубятни»). Строгая формулировка звучит так:

\text{Если } N \text{ предметов разложить по } k \text{ ящикам и } N > k, \text{ то найдётся ящик минимум с двумя предметами.}

Доказательство ты только что прочитал в истории про зайцев — это и есть рассуждение от противного. Запомни его, оно работает всегда: «допустим, везде по одному — тогда всего не больше $k$ , а у нас $N > k$ , не сходится».

Но это ещё не всё. Есть обобщённая форма — и именно она вытаскивает сложные задачи. Звучит так: если разложить $N$ предметов по $k$ ящикам, то найдётся ящик, в котором не меньше чем

\left\lceil \frac{N}{k} \right\rceil

предметов. Эти скобки $\lceil\ \rceil$ — «округление вверх» (потолок): $\lceil 2{,}3 \rceil = 3$ , $\lceil 4 \rceil = 4$ . Идея та же самая: если поделить предметы по ящикам максимально ровно, в самом «загруженном» ящике всё равно наберётся хотя бы среднее, округлённое вверх. Например, 10 предметов на 3 ящика: $\lceil 10/3 \rceil = 4$ , и правда — как ни раскидывай (3+3+4 — лучший расклад), в одном будет минимум 4. Когда $N > k$ , эта дробь больше единицы, потолок даёт минимум 2 — то есть простая форма просто частный случай обобщённой.

Всё. Матчасть кончилась. Дальше — самое интересное: как этим пользоваться.

Задача-разминка: носки в темноте

Классика, с которой всё начинают. В ящике лежат носки двух цветов — чёрные и белые, навалом. Ты достаёшь их в темноте, не глядя. Сколько носков надо вытащить, чтобы гарантированно получить пару одного цвета?

Расставляем по полочкам — буквально. Что здесь клетки, а что зайцы?

Клетки — это цвета. Их два: $k = 2$ .
Зайцы — это вытащенные носки.

Берём 3 носка ( $N = 3$ ). Получаем $3 > 2$ — значит, по принципу Дирихле два носка попадут в одну «клетку», то есть окажутся одного цвета. Пара есть! А двух не хватит: можно вытащить один чёрный и один белый — и пары нет. Ответ: 3.

Чувствуешь приём? Ты не перебираешь варианты и не считаешь вероятность. Ты просто говоришь: «категорий две, предметов три — куда-то двое да попадут». Это и есть Дирихле в чистом виде.

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

Прежде чем идти дальше — давай научимся ловить такие задачи в дикой природе. Маркеры:

В условии есть слова «обязательно найдётся», «всегда существуют», «докажите, что есть». Тебя просят доказать существование, а не что-то посчитать или предъявить конкретный объект.
Встречается «хотя бы два», «не менее $m$ », «как минимум».
Есть естественное разбиение на конечное число категорий: цвета, остатки от деления, области на плоскости, дни недели.
Предметов больше, чем категорий.

Алгоритм решения всегда один:

Назначь клетки (категории).
Назначь зайцев (объекты).
Проверь, что зайцев больше ( $N > k$ ), или прикинь $\lceil N/k \rceil$ .
Вытащи нужное свойство.

Самое сложное тут — увидеть, что назначить клетками. На разминке это было очевидно (цвета), а вот дальше — уже хитрее.

Задача-классика: разность, кратная $n$

Типичная задача школьного и муниципального уровня. Дано $n + 1$ целое число. Докажи, что среди них найдутся два, разность которых делится на $n$ .

Где тут клетки? Ключевая идея: клетки — это остатки от деления на $n$ . Любое целое при делении на $n$ даёт остаток $0, 1, 2, \dots, n-1$ — всего $n$ вариантов. Это и есть наши клетки: $k = n$ .

Зайцы — наши $n + 1$ чисел. Получаем $n + 1 > n$ , и по принципу Дирихле два числа $a$ и $b$ попадут в одну клетку — то есть дадут одинаковый остаток при делении на $n$ . А раз остатки равны, их разность $a - b$ делится на $n$ нацело. Что и требовалось. $\blacksquare$

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

Задача посложнее: точки в квадрате

Шагаем к геометрии. В квадрате со стороной 2 отметили 5 точек. Докажи, что найдутся две точки на расстоянии не больше $\sqrt{2}$ друг от друга.

Здесь не сразу видно, где клетки — точки же расположены как попало. Приём: разбей квадрат сам. Делим большой квадрат $2 \times 2$ на четыре одинаковых квадратика $1 \times 1$ . Вот тебе клетки: $k = 4$ .

Зайцы — пять точек: $N = 5 > 4$ . Значит, две точки попадут в один маленький квадратик. А какое максимальное расстояние между двумя точками внутри квадрата $1 \times 1$ ? Его диагональ:

\sqrt{1^2 + 1^2} = \sqrt{2}.

Дальше диагонали внутри квадрата не убежишь, поэтому расстояние между нашими двумя точками не больше $\sqrt{2}$ . Готово. $\blacksquare$

Видишь общий мотив? Клетки не лежали в условии готовыми — ты их создал сам, разрезав фигуру. Это второй ключевой навык: иногда разбиение надо придумать.

Шаг к настоящему олимпиадному уровню

И вот финальная задача — на ней видно, чем олимпиадный Дирихле отличается от школьного. Дана последовательность из $n$ целых чисел $a_1, a_2, \dots, a_n$ . Докажи, что найдётся несколько идущих подряд, сумма которых делится на $n$ .

Тут есть тонкость: чисел всего $n$ , а делителем выступает тоже $n$ — кажется, что зайцев и клеток поровну, принцип не запустить. Нужен трюк.

Введём частичные суммы (префиксы):

S_0 = 0,\quad S_1 = a_1,\quad S_2 = a_1 + a_2,\quad \dots,\quad S_n = a_1 + \dots + a_n.

Обрати внимание на $S_{0} = 0$ — мы добавили «пустую» сумму искусственно. Зачем? Теперь у нас $n + 1$ число ( $S_{0}$ до $S_{n}$ ). Клетки — снова остатки от деления на $n$ , их $k = n$ . Зайцев $n + 1 > n$ — Дирихле срабатывает: два префикса $S_{i}$ и $S_{j}$ (пусть $i < j$ ) дают одинаковый остаток. Значит, их разность делится на $n$ :

S_j - S_i = a_{i+1} + a_{i+2} + \dots + a_j \equiv 0 \pmod{n}.

А эта разность — ровно сумма подряд идущих чисел от $a_{i+1}$ до $a_{j}$ . Что и требовалось доказать. $\blacksquare$

Главный приём здесь — искусственно добавленный $S_{0} = 0$ . Без него зайцев ровно $n$ , и принцип не запускается. С ним — $n + 1$ , и всё взлетает. Вот эта способность «дорисовать лишний объект, чтобы перевес появился» и есть признак того, что ты вышел на олимпиадный уровень владения приёмом.

Где это встречается и что делать дальше

Дирихле — рабочая лошадь олимпиад: школьный и муниципальный этап ВсОШ, перечневые олимпиады, теория чисел, комбинаторная геометрия. Маркеры «докажите, что найдётся / хотя бы два / как минимум» будешь теперь видеть издалека. На ЕГЭ и ОГЭ он напрямую почти не спрашивается, но мышление «категории против объектов» здорово помогает в задачах на делимость и в олимпиадной части.

Запомни три навыка, которые мы прокачали:

Найти клетки — иногда они в условии (цвета), иногда это остатки от деления, иногда их надо нарисовать самому (разрезать квадрат).
Посчитать перевес — $N > k$ для простой формы или $\lceil N/k \rceil$ для оценки «сколько минимум».
Добавить лишний объект (как $S_{0} = 0$ ), когда зайцев чуть-чуть не хватает.

Дальше — только практика: приём ставится на 5–10 решённых задачах, не больше. В банке Ботан Бро есть олимпиадные задачи на Дирихле с разбором — порешай их подряд, и приём ляжет на автомате. А если где-то застрянешь — Бро рядом, разберёмся вместе.