Принцип Дирихле

Если кроликов больше, чем клеток, в какой-то клетке точно сидят минимум двое — очевидно и неожиданно мощно.

Принцип Дирихле — если $n+1$ предмет разложить по $n$ ящикам, то хотя бы в одном ящике окажется не меньше двух предметов.

Этот принцип кажется до смешного очевидным, но именно из него выводят красивые и совсем не очевидные утверждения. Его называют «принципом ящиков» или «принципом голубей и голубятен».

Формулировка и обобщение

В общем виде: если разложить $N$ предметов по $k$ ящикам, то найдётся ящик, содержащий не менее

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

предметов (здесь $\lceil x \rceil$ — округление вверх). Например, среди любых 13 человек обязательно найдутся двое, родившихся в один месяц: предметов 13, ящиков (месяцев) 12, значит, $\lceil 13/12 \rceil = 2$ человека делят месяц.

Классическое следствие про знакомства

from math import ceil

# В группе из N людей минимум сколько разделят один месяц рождения?
for N in [13, 25, 100]:
    months = 12
    guaranteed = ceil(N / months)
    print(f"{N:>3} человек: хотя бы {guaranteed} родились в один месяц")

# Среди любых 5 точек в единичном квадрате
# две на расстоянии не больше корня из 2 деленного на 2
print("--- ящики для точек ---")
print("Квадрат делим на 4 части -> 5 точек -> минимум", ceil(5 / 4), "в одной части")

Вывод:

 13 человек: хотя бы 2 родились в один месяц
 25 человек: хотя бы 3 родились в один месяц
100 человек: хотя бы 9 родились в один месяц
--- ящики для точек ---
Квадрат делим на 4 части -> 5 точек -> минимум 2 в одной части

Как работает под капотом

Сила принципа в том, что он гарантирует существование, ничего не строя. Классический пример: среди любых пяти точек в единичном квадрате найдутся две на расстоянии не больше $\frac{\sqrt2}{2}$. Доказательство: разобьём квадрат на четыре одинаковых квадратика со стороной $1/2$ (ящики). Точек пять, ящиков четыре — по принципу Дирихле в какой-то квадратик попадут две точки. А диагональ маленького квадратика равна $\frac{\sqrt2}{2}$, значит, эти две точки не дальше неё. Мы доказали факт о расстоянии, ни разу не указав конкретные точки — в этом и магия.

Частые ошибки

Принцип гарантирует ровно $\lceil N/k \rceil$, не больше: при 25 людях гарантированы трое в одном месяце, но не четверо (хотя на практике может оказаться и больше). Не путайте «существует ящик с двумя» с «во всех ящиках по два». И помните: принцип ничего не говорит, в каком именно ящике, — только что такой ящик есть.

Итог

$n+1$ предмет в $n$ ящиках — где-то минимум два.
Обобщение: найдётся ящик с $\ge \lceil N/k \rceil$ предметами.
Принцип доказывает существование, не указывая конкретику.
Применяется в геометрии, теории чисел и информатике.