Принцип включения-исключения и принцип Дирихле

Два изящных приёма: считать объединения без двойного учёта (включение-исключение) и гарантировать совпадения (принцип Дирихле).

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

Зачем нужны эти принципы

Включение-исключение отвечает на вопрос «сколько объектов обладают хотя бы одним из свойств» без двойного счёта — это и подсчёт в базах данных, и теория вероятностей, и решето в теории чисел. Принцип Дирихле — обманчиво простой, но мощнейший инструмент доказательств существования: он гарантирует, что что-то обязательно совпадёт, не указывая, где именно. На нём держатся доказательства про хеш-коллизии, сжатие данных (нельзя сжать всё без потерь — это Дирихле!), и десятки олимпиадных задач.

Включение-исключение: считаем объединение честно

Мы уже знаем для двух множеств: |A ∪ B| = |A| + |B| − |A ∩ B|. Сложили, вычли посчитанное дважды. А для трёх множеств?

|A ∪ B ∪ C| = |A| + |B| + |C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|

Логика «включаем-исключаем» по уровням: прибавляем одиночные множества, вычитаем все попарные пересечения (мы их переучли), прибавляем тройное пересечение (его мы и переучли, и перевычли — нужно вернуть). Знаки чередуются: плюс, минус, плюс... Это и есть принцип включения-исключения.

Разбор: числа, делящиеся на 2, 3 или 5

Сколько чисел от 1 до 100 делятся хотя бы на одно из 2, 3, 5? Обозначим A, B, C — множества кратных 2, 3, 5. Кратных d среди 1..100 ровно ⌊100/d⌋ штук. Считаем по формуле и сразу проверяем перебором.

N = 100
def cnt(d):
    return N // d        # сколько чисел 1..N делятся на d

# A: кратные 2, B: кратные 3, C: кратные 5
incl_excl = (cnt(2) + cnt(3) + cnt(5)
             - cnt(6) - cnt(10) - cnt(15)   # попарные: 2·3, 2·5, 3·5
             + cnt(30))                       # тройное: 2·3·5

# Прямой перебор для проверки
brute = sum(1 for x in range(1, N + 1)
            if x % 2 == 0 or x % 3 == 0 or x % 5 == 0)

print("По формуле включения-исключения:", incl_excl)
print("Прямым перебором:               ", brute)

Вывод:

По формуле включения-исключения: 74
Прямым перебором:                74

Формула дала 74 — ровно столько же, сколько прямой перебор. Без вычитания пересечений мы получили бы 50 + 33 + 20 = 103 — сильно завышено, потому что, например, число 6 (кратное и 2, и 3) посчитано дважды. Включение-исключение аккуратно убирает этот двойной (и тройной) учёт.

Принцип Дирихле: гарантия совпадения

Принцип Дирихле (в англоязычной литературе — «принцип голубей и ящиков», pigeonhole) звучит почти как трюизм: если предметов больше, чем ящиков, то в каком-то ящике их минимум два. Но из этой простоты вырастают неочевидные следствия.

• Среди любых 13 человек хотя бы двое родились в один месяц (13 «голубей», 12 «месяцев-ящиков»).
• В любой группе из 367 человек хотя бы у двоих совпадает день рождения (366 возможных дат с учётом 29 февраля).
• В Москве есть хотя бы два человека с одинаковым числом волос на голове (волос у человека меньше нескольких сотен тысяч, а людей — миллионы).

Заметь силу метода: он гарантирует существование совпадения, но не говорит, где оно. Это доказательство «чистого существования».

Обобщённый принцип Дирихле

Если разложить m предметов по n ящикам, то в каком-то ящике будет не меньше ⌈m/n⌉ предметов (округление вверх). Например, 100 писем по 9 ящикам — в каком-то минимум ⌈100/9⌉ = 12. Проверим базовый принцип Дирихле на симуляции.

import random
from collections import defaultdict

# 13 человек по 12 месяцам — Дирихле гарантирует совпадение
random.seed(5)
birth_months = [random.randint(1, 12) for _ in range(13)]

count = defaultdict(int)
for m in birth_months:
    count[m] += 1

max_in_one = max(count.values())
print("Месяцы рождения 13 человек:", birth_months)
print("Максимум людей в одном месяце:", max_in_one)
print("Минимум 2 гарантировано принципом Дирихле:", max_in_one >= 2)

Вывод:

Месяцы рождения 13 человек: [10, 5, 12, 6, 12, 12, 11, 9, 1, 8, 4, 11, 1]
Максимум людей в одном месяце: 3
Минимум 2 гарантировано принципом Дирихле: True

13 человек, 12 месяцев — и действительно нашёлся месяц с тремя совпадениями (даже больше гарантированных двух). Принцип Дирихле не зависит от случая: при любом раскладе 13 по 12 совпадение обязано быть. Это и есть его ценность — гарантия, а не вероятность.

Связь принципов с информатикой

Принцип Дирихле — это математическое сердце многих фактов CS. Хеш-коллизии: если объектов больше, чем значений хеша, коллизия неизбежна. Сжатие без потерь: нельзя сжать все файлы — иначе разные файлы отобразились бы в один код (а это Дирихле, обратить нельзя). Включение-исключение, в свою очередь, — основа быстрых подсчётов и «решета» при поиске простых чисел.

Где прячутся биномиальные коэффициенты: вероятности и подбрасывание монет

Биномиальные коэффициенты — это мост к теории вероятностей. Подбросим монету n раз: какова вероятность выпадения ровно k орлов? Всего исходов 2^n (каждый бросок — орёл или решка), а благоприятных — это число способов выбрать, в каких k из n бросков выпал орёл, то есть C(n, k). Получается биномиальное распределение: вероятность C(n, k) / 2^n.

Именно поэтому строка треугольника Паскаля описывает форму «колокола»: в середине (около k = n/2) коэффициенты самые большие — равное число орлов и решек самое вероятное, а крайние случаи (все орлы или все решки) — самые редкие. Этот «колокол» при больших n превращается в знаменитую нормальную кривую Гаусса. Так абстрактный треугольник Паскаля оказывается описанием случайности в реальном мире: от контроля качества на производстве до A/B-тестов и азартных игр. Сочетания, которые мы вывели для подсчёта команд, неожиданно управляют вероятностями.

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

• Забывать знаки во включении-исключении. Попарные пересечения вычитаются, тройные прибавляются, и так далее по чередованию. Пропуск уровня даёт неверный ответ.
• Думать, что Дирихле указывает, где совпадение. Он гарантирует, что совпадение есть, но не говорит, в каком именно ящике. Это доказательство существования.
• Неверно считать «ящики». Сила задачи на Дирихле — в удачном выборе ящиков. Неправильные ящики — и принцип не сработает или даст слабую оценку.

Итог

• Включение-исключение: |A∪B∪C| = ΣодиночныеΣ − Σпопарные + тройное, знаки чередуются.
• Оно убирает двойной учёт общих элементов при подсчёте объединений.
• Принцип Дирихле: предметов больше ящиков ⇒ где-то минимум два; обобщённо — минимум ⌈m/n⌉.
• Дирихле гарантирует существование совпадения (хеш-коллизии, пределы сжатия), не указывая где.