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

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

Принцип включения-исключения: |A ∪ B| = |A| + |B| − |A ∩ B|, и аналогично для большего числа множеств со знакочередованием.

Зачем это в олимпиадах

Когда нужно сосчитать объекты, удовлетворяющие хотя бы одному из условий («числа, делящиеся на 2, 3 или 5»), прямой подсчёт даёт двойной учёт пересечений. Принцип включения-исключения (ПВИ) аккуратно вычитает лишнее. Он стоит за формулой беспорядков, подсчётом взаимно простых чисел (функция Эйлера), задачами «сколько перестановок без неподвижных точек». Принцип Дирихле — другой инструмент: он не считает, а доказывает существование: «среди n+1 чисел два дают одинаковый остаток по модулю n». Оба — классика олимпиад.

Включения-исключения: интуиция

Сложив |A| + |B|, мы дважды посчитали элементы пересечения A ∩ B — вычтем его один раз: |A ∪ B| = |A| + |B| − |A ∩ B|. Для трёх множеств добавляем тройное пересечение обратно (его вычли трижды и прибавили трижды): |A ∪ B ∪ C| = |A|+|B|+|C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|. Общий принцип: складываем одиночные, вычитаем парные, прибавляем тройные и так далее со знаком (−1)^{размер+1}.

# Сколько чисел от 1 до 100 делятся на 2, 3 или 5?
n = 100
def cnt(d):
    return n // d         # сколько кратных d в [1, n]

by_formula = (cnt(2) + cnt(3) + cnt(5)
              - cnt(6) - cnt(10) - cnt(15)   # попарные НОК: 2·3, 2·5, 3·5
              + cnt(30))                      # тройное: 2·3·5
print(by_formula)

# проверка прямым перебором
brute = sum(1 for x in range(1, 101) if x % 2 == 0 or x % 3 == 0 or x % 5 == 0)
print(brute)

Вывод:

74
74

Формула и перебор дали 74. Обратите внимание: пересечение «делится на 2 и на 3» — это «делится на 6» (НОК), поэтому в пересечениях стоят 6, 10, 15, 30. Перебор работает за O(n), а ПВИ — за число подмножеств условий (здесь 7 слагаемых), что критично при больших n.

Классическая задача: беспорядки

Беспорядок — перестановка без неподвижных точек (никто не остался на своём месте). Сколько их? Применим ПВИ к «плохим» событиям Aᵢ = «элемент i на своём месте». Перестановок, где зафиксировано j конкретных позиций, ровно (n−j)!, а выбрать эти позиции можно C(n,j) способами. Со знакочередованием получаем:

D(n) = ∑_j=0ⁿ (−1)^j · C(n, j) · (n − j)!

import math
from itertools import permutations

def derangements(n):
    return sum((-1) ** j * math.comb(n, j) * math.factorial(n - j)
               for j in range(n + 1))

print(derangements(4))     # формула

# проверка перебором: перестановки {0,1,2,3} без p[i]==i
count = sum(1 for p in permutations(range(4))
            if all(p[i] != i for i in range(4)))
print(count)
print([derangements(n) for n in range(1, 8)])

Вывод:

9
9
[0, 1, 2, 9, 44, 265, 1854]

Формула совпала с перебором: для n=4 ровно 9 беспорядков. Любопытно, что D(n)/n! → 1/e ≈ 0.368 — доля беспорядков среди всех перестановок стремится к 1/e. Это красивый мост от комбинаторики к анализу.

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

Принцип Дирихле (про голубей и ящики): если n+1 предмет разложить по n ящикам, то в каком-то ящике окажется хотя бы два предмета. Обобщённо: при k·n+1 предметах в n ящиках найдётся ящик с ≥ k+1 предметами.

Это очевидное утверждение — на удивление мощный инструмент доказательства существования. Оно не говорит, где совпадение, лишь что оно есть. Классический пример: среди любых n+1 целых чисел найдутся два с одинаковым остатком по модулю n (ящики — остатки 0…n−1, предметов n+1). Отсюда, в частности, следует, что разность этих двух чисел делится на n.

# Среди любых n+1 чисел найдутся два с равным остатком по модулю n.
# Демонстрация: возьмём n=10 и 11 произвольных чисел.
n = 10
numbers = [3, 14, 27, 100, 41, 58, 6, 73, 89, 22, 55]
seen = {}
for x in numbers:
    r = x % n
    if r in seen:
        print(f"Совпадение остатка {r}: {seen[r]} и {x}, "
              f"разность {x - seen[r]} делится на {n}: {(x - seen[r]) % n == 0}")
        break
    seen[r] = x

Вывод:

Совпадение остатка 3: 3 и 73, разность 70 делится на 10: True

Перебирая остатки, мы гарантированно нашли совпадение — иначе 11 чисел дали бы 11 различных остатков, а их всего 10. Это и есть Дирихле в действии: существование коллизии без указания, какой именно.

Разбор задачи: число сюръекций (раскраски без пропусков)

Ещё один шедевр ПВИ — подсчёт сюръекций: сколько функций из множества [n] на множество [k] используют все k значений? Эквивалентно: сколькими способами раскрасить n различных объектов в k цветов так, чтобы каждый цвет был использован. Всего функций kⁿ; вычтем те, что пропускают хотя бы один цвет. По ПВИ: ∑_j (−1)^j C(k, j) (k−j)ⁿ — выбираем j «запрещённых» цветов и считаем функции в оставшиеся.

import math
from itertools import product

def surjections(n, k):
    return sum((-1) ** j * math.comb(k, j) * (k - j) ** n
               for j in range(k + 1))

print(surjections(4, 2))     # функции из 4 элементов на 2 значения
# проверка перебором: функции [4]->[2], использующие оба значения
brute = sum(1 for f in product(range(2), repeat=4) if set(f) == {0, 1})
print(brute)
print(surjections(5, 3))     # на 3 значения
print(sum(1 for f in product(range(3), repeat=5) if set(f) == {0, 1, 2}))

Вывод:

Формула совпала с перебором: из 4 элементов на 2 значения ведут 14 сюръекций (всего функций 2⁴=16, минус 2 постоянные). Число сюръекций связано с числами Стирлинга второго рода: surj(n,k) = k! · S(n,k). ПВИ здесь — единственный разумный способ счёта: прямой перебор экспоненциален, а формула считается за O(k·log n) с быстрым возведением.

Подводные камни

Знаки в ПВИ. Нечётные размеры подмножеств — со знаком плюс, чётные — минус (для формулы объединения). Перепутать знак = неверный ответ.
Пересечения = НОК/совместные условия. «Делится на 2 и на 3» — это «делится на 6», а не на 5.
Экспоненциальный рост слагаемых. ПВИ по m условиям даёт 2^m слагаемых — применим только при небольшом m.
Дирихле не конструктивен. Он доказывает существование, но не находит объект — для поиска нужен отдельный алгоритм.

Итог

ПВИ считает мощность объединения со знакочередованием по размеру пересечений.
Беспорядки: D(n)=∑(−1)^jC(n,j)(n−j)!, доля → 1/e.
Пересечение делимостей — это делимость на НОК.
Принцип Дирихле доказывает существование совпадений (n+1 предмет в n ящиков).