Биекция в комбинаторике: как доказать равенство двух счётов, построив соответствие?
На олимпиадах часто доказывают комбинаторные равенства «построением биекции», но я не понимаю, как именно это работает и почему биекция = доказательство. Можете показать на конкретном примере (например, что число подмножеств чётного размера равно числу подмножеств нечётного размера)?
2 ответа
Биекция — это взаимно однозначное соответствие между двумя множествами A и B. Если ты построил такое соответствие (каждому a∈A сопоставлен ровно один b∈B и наоборот), то |A| = |B| — это и есть доказательство равенства счётов, БЕЗ вычисления самих чисел.
Пример: подмножеств n-элементного множества чётного размера столько же, сколько нечётного (при n≥1). Зафиксируем элемент x. Биекция: подмножеству S сопоставим S △ {x} (добавить x, если его нет; убрать, если есть). Это меняет чётность размера ровно на 1 (чётное ↔ нечётное) и обратимо (применив дважды, вернёмся к S). Значит чётных и нечётных подмножеств поровну → каждого по 2^{n−1}.
Это комбинаторное доказательство тождества Σ (−1)^k C(n,k) = 0. Алгебраически оно следует из (1−1)^n = 0, но биекция показывает, ПОЧЕМУ это так, на уровне объектов.
Кода нет — это техника доказательства. Но она бесценна на контесте: вместо тяжёлой алгебры строишь явное отображение и сразу получаешь равенство, а заодно часто и способ конструктивно перечислять объекты.
Ещё классика — биекция «правильные скобочные последовательности ↔ монотонные пути под диагональю» (обе считаются Каталаном): открывающая скобка = шаг вверх/вправо, закрывающая = другой шаг, условие «баланс не уходит в минус» = «путь не пересекает диагональ». Построил соответствие — доказал, что объектов поровну, и можешь считать любым из двух способов. Главное — проверить, что отображение действительно ВЗАИМНО однозначно (есть обратное), иначе это не биекция.