Теория курса

Комбинаторика. Книга 2

Book 2. Olympiad Combinatorics Methods

1. Продвинутый двойной подсчёт
2. Метод включений-исключений
3. Биекции и кодирование объектов
4. Экстремальный принцип
5. Инварианты II и моноинварианты
6. Идеи Рамсея
7. Графы II
8. Паросочетания и введение в теорему Холла
9. Производящие функции I

Глава

Продвинутый двойной подсчёт

Модуль развивает двойной подсчёт до подсчёта пар, троек, инцидентностей, пересечений и неравенств через среднее.

Ключевая идея Двойной подсчёт — это выбор одного множества объектов и подсчёт его двумя способами. В продвинутых задачах объектами часто являются не сами элементы, а пары, тройки, инцидентности, пересечения или пути. Метод особенно силён, когда прямой подсчёт труден, но сумма по строкам равна сумме по столбцам, а среднее значение заставляет существовать “хороший” объект. Основные факты Если \(I=\{(x,A):x\in A\}\), то \(|I|=\sum_A |A|=\sum_x d(x)\), где \(d(x)\) — число множеств, содержащих \(x\). Среднее: если сумма \(S\) распределена между \(n\) объектами, то некоторый объект имеет значение не меньше \(\frac Sn\). Число пар элементов внутри множеств равно \(\sum_A \binom{|A|}{2}\). Если каждая пара элементов может встречаться не более одного раза, то \(\sum_A \binom{|A|}{2}\le\binom n2\). В графе сумма степеней равна \(2E\). Когда применять метод Применяйте метод, когда в условии есть “каждый объект связан с…”, строки и столбцы, семейства множеств, пересечения, знакомства, турниры, пути длины \(2\), или нужно доказать существование объекта через среднее. Как распознать метод Ищите скрытые пары: “элемент принадлежит множеству”, “ученик решил задачу”, “вершина инцидентна ребру”, “две строки имеют общий отмеченный столбец”. Если такие пары можно считать с двух сторон, это почти наверняка двойной подсчёт. Типичные ошибки Считать исходные объекты вместо правильных пар или троек. Забывать, что один объект может учитываться несколько раз. Использовать среднее без перехода к целому числу: нужны \(\lceil x\rceil\) или строгая оценка. Путать “не более одного общего элемента” и “ровно один общий элемент”. Доказывать только формулу, но не связывать её с требуемым существованием. Мини-чеклист Назовите объект, который считаете: пары, тройки, инцидентности. Посчитайте его “по левым объектам” и “по правым объектам”. Если нужна оценка, замените точный подсчёт неравенством. Если нужна существование, сравните с средним. Проверьте, не посчитали ли один и тот же объект дважды без контроля.

Пример 1. Инцидентности Самый базовый вид двойного подсчёта. Задача. В классе \(24\) ученика посещают кружки. Каждый ученик посещает ровно \(3\) кружка. Докажите, что если кружков \(8\), то некоторый кружок посещают не меньше \(9\) учеников. Решение. Посчитаем пары \((ученик, кружок)\), где ученик посещает этот кружок. По ученикам таких пар \(24\cdot3=72\). По кружкам среднее число учеников равно \(\frac{72}{8}=9\). Значит, некоторый кружок имеет не меньше \(9\) участников. Комментарий. Не надо знать распределение по кружкам; достаточно общего числа инцидентностей. Пример 2. Сумма степеней графа Графы — естественный язык для многих задач о связях. Задача. Докажите, что в любом графе число вершин нечётной степени чётно. Решение. Сумма степеней всех вершин равна \(2E\), где \(E\) — число рёбер, потому что каждое ребро добавляет \(1\) к степеням двух концов. Значит, сумма степеней чётна. Сумма чётных степеней чётна, поэтому сумма нечётных степеней тоже чётна. Это возможно только при чётном числе нечётных слагаемых. Комментарий. Это двойной подсчёт пар \((вершина, ребро)\), где вершина инцидентна ребру. Пример 3. Среднее по элементам Часто нужно доказать существование элемента с большой нагрузкой. Задача. Дано \(m\) подмножеств множества из \(n\) элементов, каждое имеет размер не меньше \(r\). Докажите, что некоторый элемент входит хотя бы в \(\left\lceil\frac{mr}{n}\right\rceil\) подмножеств. Решение. Считаем пары \((x,A)\), где \(x\in A\). По множествам таких пар не меньше \(mr\). По элементам это сумма чисел \(d(x)\), где \(d(x)\) — сколько множеств содержат \(x\). Среднее \(d(x)\) не меньше \(\frac{mr}{n}\), значит некоторый \(d(x)\) не меньше потолка этого числа. Комментарий. Это стандартный “average argument”. Пример 4. Тождество через выбор Комбинаторное тождество лучше доказывать подсчётом объектов. Задача. Докажите \(\sum_{k=0}^{n} k\binom nk=n2^{n-1}\). Решение. Посчитаем пары \((A,x)\), где \(A\subseteq\{1,\ldots,n\}\) и \(x\in A\). Если сначала выбрать \(A\) размера \(k\), получаем \(\sum k\binom nk\). Если сначала выбрать \(x\), есть \(n\) вариантов, а остальные элементы подмножества выбираются произвольно: \(2^{n-1}\) вариантов. Итого \(n2^{n-1}\). Комментарий. Левая часть группирует по размеру множества, правая — по отмеченному элементу. Пример 5. Пары внутри множеств Переход от элементов к парам резко усиливает метод. Задача. Есть \(m\) подмножеств \(k\)-элементного размера в \(n\)-элементном множестве. Любые два подмножества имеют не более одного общего элемента. Докажите \(m\binom{k}{2}\le\binom n2\). Решение. Посчитаем пары \((\{x,y\},A)\), где \(x,y\in A\), \(x\ne y\). Каждое множество \(A\) даёт \(\binom{k}{2}\) пар, всего \(m\binom{k}{2}\). С другой стороны, любая пара элементов \(\{x,y\}\) может лежать не более чем в одном из данных множеств, иначе два множества имели бы два общих элемента. Поэтому таких пар не больше \(\binom n2\). Комментарий. Это типичный double-counting inequality. Пример 6. Таблица нулей и единиц Строки и столбцы часто дают два естественных подсчёта. Задача. В таблице \(10\times10\) отмечено \(46\) клеток. Докажите, что есть строка или столбец, содержащие не меньше \(5\) отмеченных клеток. Решение. Посчитаем пары \((отмеченная клетка, линия)\), где линия — строка или столбец, содержащая клетку. Каждая отмеченная клетка лежит ровно на двух линиях, значит всего \(92\) пар. Линий \(20\), среднее число отмеченных клеток на линии равно \(4.6\). Поэтому некоторая линия содержит хотя бы \(5\) отмеченных клеток. Комментарий. Иногда выгодно считать не строки отдельно и столбцы отдельно, а все линии сразу. Пример 7. Среднее пересечение Пересечения семейств множеств считаются через степени элементов. Задача. Есть \(8\) трёхэлементных подмножеств \(5\)-элементного множества. Докажите, что два из них пересекаются хотя бы по двум элементам. Решение. Пусть \(d(x)\) — число выбранных подмножеств, содержащих элемент \(x\). Тогда \(\sum d(x)=8\cdot3=24\). Число троек \((x,\{A,B\})\), где \(x\in A\cap B\), равно \(\sum_x\binom{d(x)}2\). При сумме \(24\) по \(5\) элементам минимальная сумма \(\sum\binom{d(x)}2\) получается при максимально ровном распределении \(5,5,5,5,4\), и равна \(46\). Пар подмножеств всего \(\binom82=28\). Если бы каждое пересечение имело размер не больше \(1\), сумма размеров всех попарных пересечений была бы не больше \(28\), противоречие. Комментарий. Это пример, где двойной подсчёт соединяется с выпуклостью. Пример 8. Тройки Иногда правильный объект — не пара, а тройка. Задача. Докажите \(\sum_{A\subseteq[n]}\binom{|A|}{2}=\binom n2 2^{n-2}\). Решение. Считаем пары \((A,\{x,y\})\), где \(A\subseteq[n]\) и \(x,y\in A\). Если сначала выбрать \(A\), получаем левую часть. Если сначала выбрать пару \(\{x,y\}\), есть \(\binom n2\) способов, а остальные \(n-2\) элементов можно включать или не включать независимо: \(2^{n-2}\) способов. Комментарий. Такие тождества хорошо тренируют выбор объекта для подсчёта.

Глава

Метод включений-исключений

Модуль развивает включения-исключения для запрещённых условий, беспорядков, сюръекций, неподвижных точек и распределений.

Ключевая идея Метод включений-исключений считает объекты, которые удовлетворяют хотя бы одному из условий, или наоборот избегают запрещённых условий. Главная идея: сначала сложить слишком много, затем вычесть пересечения, затем вернуть тройные пересечения и так далее. Основные факты \(|A\cup B|=|A|+|B|-|A\cap B|\). Для трёх множеств добавляются попарные пересечения и тройное пересечение. Количество объектов без запрещённых свойств равно \(\sum (-1)^i\) умножить на число объектов с выбранными \(i\) запретами. Число беспорядков: \(D_n=n!\sum_{i=0}^{n}\frac{(-1)^i}{i!}\). Число сюръекций из \(n\)-элементного множества в \(m\)-элементное равно \(\sum_{i=0}^{m}(-1)^i\binom mi(m-i)^n\). Когда применять метод Используйте метод, когда есть слова “хотя бы одно”, “ни одно”, “неподвижная точка”, “запрещённая позиция”, “каждый цвет используется”, “каждая коробка непуста”, “не делится на данные числа”. Как распознать метод Если прямой подсчёт объектов с ограничениями неудобен, посчитайте дополнение. Если объекты нарушают несколько запретов одновременно, простое вычитание даст ошибку — нужен принцип включений-исключений. Типичные ошибки Вычесть объекты с двумя нарушениями дважды и не вернуть их. Путать “хотя бы один запрет нарушен” и “ровно один запрет нарушен”. Забывать, что после фиксации \(i\) неподвижных точек переставляются \(n-i\) объектов. В задачах с функциями путать “использованы все значения” и “значения различны”. Мини-чеклист Назовите запрещённые события \(A_1,\ldots,A_m\). Решите, считаете ли объединение запретов или дополнение к нему. Для выбранных \(i\) запретов посчитайте, сколько объектов им удовлетворяет одновременно. Поставьте знак \((-1)^i\). Проверьте крайние случаи: \(i=0\), \(i=m\), маленькие \(n\).

Пример 1. Два множества Базовая формула нужна как язык для всех следующих задач. Задача. Докажите формулу \(|A\cup B|=|A|+|B|-|A\cap B|\). Решение. При сложении \(|A|+|B|\) каждый элемент из \(A\setminus B\) и \(B\setminus A\) посчитан один раз, а каждый элемент из \(A\cap B\) — дважды. Чтобы оставить его один раз, вычитаем \(|A\cap B|\). Комментарий. Важно понимать не формулу, а причину знака минус. Пример 2. Три делителя Числа с несколькими признаками часто требуют включений-исключений. Задача. Сколько чисел от \(1\) до \(1000\) делятся хотя бы на одно из чисел \(2,3,5\)? Решение. Получаем \(\left\lfloor\frac{1000}{2}\right\rfloor+\left\lfloor\frac{1000}{3}\right\rfloor+\left\lfloor\frac{1000}{5}\right\rfloor-\left\lfloor\frac{1000}{6}\right\rfloor-\left\lfloor\frac{1000}{10}\right\rfloor-\left\lfloor\frac{1000}{15}\right\rfloor+\left\lfloor\frac{1000}{30}\right\rfloor=500+333+200-166-100-66+33=734\). Комментарий. Каждое попарное пересечение вычитается, тройное возвращается. Пример 3. Все буквы использованы Сюръекция — это “каждое значение используется”. Задача. Сколько слов длины \(7\) над алфавитом \(\{A,B,C\}\) содержат все три буквы? Решение. Всего слов \(3^7\). Вычтем слова, в которых отсутствует хотя бы одна буква. Если выбрана отсутствующая буква, остаётся \(2^7\) слов; таких выборов \(3\). Слова, в которых отсутствуют две буквы, были вычтены дважды, их нужно вернуть: \(3\cdot1^7\). Ответ: \(3^7-3\cdot2^7+3=1806\). Комментарий. Это формула сюръекций в маленьком виде. Пример 4. Беспорядки Неподвижные точки — главный классический пример. Задача. Сколько перестановок \(5\) элементов не имеют неподвижных точек? Решение. Пусть \(A_i\) — событие, что \(i\)-й элемент стоит на месте. По включениям-исключениям число перестановок без неподвижных точек равно\[5!-\binom51 4!+\binom52 3!-\binom53 2!+\binom54 1!-\binom55 0!=44.\] Комментарий. После выбора фиксированных точек остальные элементы переставляются свободно. Пример 5. Ровно \(k\) неподвижных точек Иногда сначала выбирают хорошие фиксированные точки, затем запрещают остальные. Задача. Сколько перестановок \(n\) элементов имеют ровно \(k\) неподвижных точек? Решение. Сначала выбираем эти \(k\) элементов: \(\binom nk\). Остальные \(n-k\) элементов не должны иметь неподвижных точек среди себя, значит их можно переставить \(D_{n-k}\) способами. Ответ: \(\binom nkD_{n-k}\). Комментарий. Здесь включения-исключения спрятано внутри \(D_{n-k}\). Пример 6. Запрещённые позиции Перестановки с ограничениями удобно считать через события. Задача. Сколько перестановок чисел \(1,\ldots,8\) имеют \(1,2,3\) не на своих местах? Решение. Запреты только для первых трёх чисел. По включениям-исключениям получаем\[8!-\binom31 7!+\binom32 6!-\binom33 5!=40320-15120+2160-120=27240.\] Комментарий. Не все элементы обязаны избегать своих мест, только \(1,2,3\). Пример 7. Сюръекции Формула включений-исключений для функций. Задача. Сколько сюръекций из \(6\)-элементного множества в \(3\)-элементное? Решение. Всего функций \(3^6\). Вычитаем функции, пропускающие выбранное значение: \(\binom31 2^6\). Возвращаем функции, пропускающие два значения: \(\binom32 1^6\). Ответ: \(3^6-3\cdot2^6+3=540\). Комментарий. Это тот же подсчёт, что и слова с использованием всех букв. Пример 8. Общая формула Понимание вклада одного объекта объясняет все знаки. Задача. Объясните, почему объект, нарушающий ровно \(r\) запретов, в сумме \(\sum_{i=0}^m(-1)^i\binom ri\) учитывается как \(0\), если \(r>0\), и как \(1\), если \(r=0\). Решение. Если объект нарушает ровно \(r\) запретов, то он попадает в пересечение любой выбранной группы из \(i\) этих \(r\) запретов. Его общий вклад равен \(\sum_{i=0}^r(-1)^i\binom ri=(1-1)^r\). При \(r>0\) это \(0\), а при \(r=0\) вклад равен \(1\). Комментарий. Это лучшее объяснение общей формулы.

Глава

Биекции и кодирование объектов

Модуль учит строить взаимно однозначные соответствия: подмножества и строки, пути и слова, композиции и перегородки, разбиения и диаграммы, Catalan-style отражения.

Ключевая идея Биекция доказывает, что два множества имеют одинаковое число элементов, не вычисляя оба числа отдельно. Нужно построить правило, которое каждому объекту первого типа сопоставляет ровно один объект второго типа, и обратно. В олимпиадной комбинаторике биекция часто превращает неудобный объект в код: путь в слово, подмножество в бинарную строку, распределение в строку из звёздочек и перегородок, разбиение в диаграмму. Основные факты Подмножества \(n\)-элементного множества биективны бинарным строкам длины \(n\). Монотонные пути из \((0,0)\) в \((a,b)\) биективны словам из \(a\) букв \(R\) и \(b\) букв \(U\). Неотрицательные решения \(x_1+\cdots+x_k=n\) биективны строкам из \(n\) звёздочек и \(k-1\) перегородок. Дополнение подмножества даёт биекцию между \(k\)-подмножествами и \((n-k)\)-подмножествами. Отражение плохих путей часто даёт точную формулу для Catalan-style условий. Когда применять метод Метод особенно полезен, когда ответ похож на простую формулу, но прямой подсчёт громоздок; когда нужно доказать тождество; когда объекты можно “закодировать” последовательностью решений; или когда есть ограниченные пути, скобки, разбиения, выборы без соседних элементов. Как распознать метод Сигналы: “докажите, что количеств одинаково”, “найдите число способов” с очень разными объектами, “слово/путь/подмножество/распределение”, “без соседних”, “не выше диагонали”, “разбиение на части”. Часто полезно спросить: какую информацию нужно записать, чтобы восстановить объект? Типичные ошибки Построить отображение, но не доказать обратимость. Потерять объекты с нулевыми частями в stars and bars. Считать путь и слово похожими, но не указать точное соответствие шагов. В отражении путей отражать не с первого запрещённого шага. Смешивать упорядоченные композиции и неупорядоченные разбиения. Мини-чеклист Опишите объект слева и объект справа. Сформулируйте прямое отображение. Покажите, как восстановить исходный объект. Проверьте границы: нули, пустые блоки, крайние пути. Если есть запрет, попробуйте биекцию с плохими объектами или отражение.

Пример 1. Подмножества и бинарные строки Самая простая биекция: объект заменяется кодом из нулей и единиц. Задача. Докажите, что у \(n\)-элементного множества ровно \(2^n\) подмножеств. Решение. Занумеруем элементы \(1,\ldots,n\). Каждому подмножеству сопоставим бинарную строку длины \(n\): на \(i\)-м месте стоит \(1\), если элемент \(i\) выбран, и \(0\), если не выбран. По строке можно однозначно восстановить подмножество. Значит, подмножеств столько же, сколько бинарных строк, то есть \(2^n\). Комментарий. Важна обратимость: строка не просто получается из подмножества, она полностью его задаёт. Пример 2. Пути и слова Путь на решётке удобно кодировать последовательностью шагов. Задача. Сколько монотонных путей ведёт из \((0,0)\) в \((4,3)\), если разрешены шаги вправо и вверх? Решение. Каждый путь состоит из \(4\) шагов \(R\) вправо и \(3\) шагов \(U\) вверх. Записав шаги по порядку, получаем слово длины \(7\) с четырьмя \(R\) и тремя \(U\). Обратно, каждое такое слово задаёт путь. Поэтому число путей равно \(\binom{7}{3}=35\). Комментарий. Это базовая биекция “путь ↔ слово”. Пример 3. Звёздочки и перегородки Распределение одинаковых предметов между разными коробками — это код с перегородками. Задача. Сколько неотрицательных решений имеет уравнение \(x_1+x_2+x_3+x_4=12\)? Решение. Запишем \(12\) звёздочек в ряд и поставим \(3\) перегородки. Число звёздочек до первой перегородки — \(x_1\), между первой и второй — \(x_2\), между второй и третьей — \(x_3\), после третьей — \(x_4\). Соседние перегородки разрешены, это даёт нулевые части. Всего нужно выбрать позиции \(3\) перегородок среди \(15\) символов, значит ответ \(\binom{15}{3}=455\). Комментарий. Это источник многих задач на композиции. Пример 4. Выбор без соседних Запрет соседства часто убирается сдвигом индексов. Задача. Сколько \(k\)-элементных подмножеств множества \(\{1,\ldots,n\}\) не содержат соседних чисел? Решение. Пусть выбранные числа \(1\le a_1<\cdots Комментарий. Это биекция со сдвигом, а не просто формула. Пример 5. Дополнение Иногда биекция настолько проста, что её легко не заметить. Задача. Докажите \(\binom nk=\binom n{n-k}\) комбинаторно. Решение. Каждому \(k\)-элементному подмножеству \(A\) сопоставим его дополнение \([n]\setminus A\), которое имеет \(n-k\) элементов. Обратное отображение такое же: дополнение дополнения равно исходному множеству. Значит, объектов поровну. Комментарий. Это хороший пример биекции-инволюции. Пример 6. Диаграммы Ферре Разбиения удобно поворачивать или отражать. Задача. Докажите, что число разбиений числа \(n\) не более чем на \(k\) частей равно числу разбиений \(n\), в которых каждая часть не превосходит \(k\). Решение. Запишем разбиение диаграммой Ферре: строки состоят из клеток, длины строк — части разбиения. Если строк не больше \(k\), то после транспонирования диаграммы число клеток в каждой строке новой диаграммы не больше \(k\). Обратное преобразование — то же транспонирование. Поэтому получаем биекцию. Комментарий. Здесь полезен рисунок, но сама идея — обратимое преобразование диаграммы. Пример 7. Отражение плохих путей Первый серьёзный Catalan-style ход. Задача. Сколько путей из \((0,0)\) в \((n,n)\) шагами \(R,U\) никогда не поднимаются выше диагонали \(y=x\)? Решение. Всего путей \(\binom{2n}{n}\). Плохие пути впервые переходят выше диагонали некоторым шагом \(U\), попадая в точку с \(y=x+1\). Отразим часть пути до этого первого перехода относительно прямой \(y=x+1\). Получится путь из \((-1,1)\) в \((n,n)\), то есть слово с \(n+1\) шагами \(R\) и \(n-1\) шагами \(U\). Таких путей \(\binom{2n}{n-1}\). Поэтому хороших путей \(\binom{2n}{n}-\binom{2n}{n-1}=\frac{1}{n+1}\binom{2n}{n}\). Комментарий. Главное — отражать до первого нарушения. Пример 8. Код Прюфера Сильная биекция: дерево превращается в последовательность. Задача. Сформулируйте идею кода Прюфера для подсчёта деревьев на вершинах \(1,\ldots,n\). Решение. Пока в дереве больше двух вершин, удаляем лист с наименьшим номером и записываем номер его соседа. Получаем последовательность длины \(n-2\) из чисел \(1,\ldots,n\). Обратно, по такой последовательности можно восстановить дерево: каждый раз берём наименьший номер, отсутствующий в текущей последовательности, соединяем его с первым элементом последовательности и удаляем этот первый элемент. В конце соединяем две оставшиеся вершины. Это биекция между помеченными деревьями и последовательностями длины \(n-2\), поэтому деревьев \(n^{n-2}\). Комментарий. Это Level 5-инструмент, но его стоит увидеть уже здесь.

Глава

Экстремальный принцип

Модуль учит выбирать максимальный или минимальный объект: самый длинный путь, минимальный контрпример, максимальную конфигурацию или крайний интервал. Метод применяется в графах, турнирах, задачах на множества и процессах.

Пример 1. Самый большой элемент Короткий пример показывает, что экстремальный выбор сам по себе уже может дать противоречие. Задача. В конечном непустом множестве положительных чисел каждое число, кроме, возможно, одного, имеет в этом множестве строго большее число. Докажите, что число, для которого такого большего числа нет, существует и единственно. Решение. Выберем в множестве максимальное число \(M\). Для него не может существовать строго большего числа из того же множества. Значит, хотя бы одно такое число есть. Если бы было два разных числа без большего, то большее из них всё равно было бы строго больше меньшего, то есть меньшее имело бы большее число. Противоречие. Следовательно, такое число единственно. Комментарий. Здесь экстремальным объектом является максимум множества. Пример 2. Самый длинный путь Этот пример — стандартная заготовка для задач на графы. Задача. В конечном графе выбран путь максимальной длины. Докажите, что все соседи его конечной вершины лежат на этом пути. Решение. Пусть путь имеет вид \(v_1v_2\ldots v_k\), и рассмотрим конечную вершину \(v_k\). Если бы у неё был сосед \(u\), не лежащий на пути, то \(v_1v_2\ldots v_k u\) был бы более длинным путём. Это невозможно, потому что исходный путь выбран максимальным. Значит, каждый сосед \(v_k\) уже входит в этот путь. Пример 3. Интервалы на прямой Иногда экстремальной величиной является не размер, а координата. Задача. Несколько отрезков на прямой попарно пересекаются. Докажите, что есть точка, принадлежащая всем отрезкам. Решение. Выберем отрезок \([a,b]\) с наименьшим правым концом \(b\). Возьмём любой другой отрезок \([c,d]\). Так как отрезки пересекаются, не может быть \(d Если бы \(b Пример 4. Минимальный связный подграф Максимум и минимум по числу рёбер часто помогают убирать лишнее. Задача. Докажите, что в любом конечном связном графе есть связный подграф, содержащий все вершины и не имеющий циклов. Решение. Среди всех связных подграфов, содержащих все вершины исходного графа, выберем подграф с минимальным числом рёбер. Он существует, потому что исходный граф сам подходит. Если в выбранном подграфе есть цикл, то можно удалить одно ребро этого цикла: связность не нарушится, ведь вокруг цикла остаётся обходной путь. Получится связный подграф с теми же вершинами и меньшим числом рёбер, что противоречит минимальности. Значит, циклов нет. Такой подграф является деревом. Пример 5. Максимальная конфигурация Здесь объект выбирается не обязательно наибольшим по размеру, а таким, к которому нельзя ничего добавить. Задача. В графе выбрано множество непересекающихся рёбер, к которому нельзя добавить ещё одно ребро, не нарушив непересечение. Докажите, что любые две вершины, не покрытые выбранными рёбрами, не соединены ребром. Решение. Пусть две непокрытые вершины \(x\) и \(y\) соединены ребром. Тогда это ребро не имеет общих вершин ни с одним из уже выбранных рёбер. Значит, его можно добавить к выбранному множеству, сохранив непересечение. Это противоречит максимальности по включению. Следовательно, таких двух непокрытых соседних вершин нет. Пример 6. Турнир и максимальная степень В турнирах экстремальным часто бывает участник с наибольшим числом побед. Задача. В турнире выберем игрока \(v\) с наибольшим числом побед. Докажите, что любой игрок либо проиграл \(v\), либо проиграл кому-то, кого победил \(v\). Решение. Рассмотрим игрока \(u\), который не проиграл \(v\), то есть победил \(v\). Предположим, что \(u\) победил всех игроков, которых победил \(v\). Тогда у \(u\) есть все победы над побеждёнными игроками \(v\), а также победа над самим \(v\). Значит, у \(u\) побед больше, чем у \(v\), что противоречит выбору \(v\). Следовательно, среди игроков, побеждённых \(v\), найдётся игрок, победивший \(u\). Пример 7. Минимальный контрпример Минимальный контрпример удобен, когда задачу можно уменьшить. Задача. Докажите, что любое целое число \(n\ge 8\) можно представить в виде \(3a+5b\), где \(a,b\) — неотрицательные целые числа. Решение. Проверим \(8=3+5\), \(9=3+3+3\), \(10=5+5\). Предположим, что утверждение неверно, и выберем наименьшее \(n\ge 8\), которое не представимо. Тогда \(n\ge 11\), поэтому \(n-3\ge 8\). По минимальности \(n\) число \(n-3\) представимо как \(3a+5b\). Тогда \(n=3(a+1)+5b\), противоречие. Значит, контрпримеров нет. Пример 8. Локальное улучшение Экстремальный принцип часто скрывается в фразе «возьмём расположение с минимальным числом нарушений». Задача. Числа \(1,2,\ldots,n\) расставлены в ряд. Разрешается менять местами соседние числа, если левое больше правого. Докажите, что процесс обязательно закончится возрастающим рядом. Решение. Назовём инверсией пару позиций \(i Число инверсий — неотрицательное целое число, поэтому оно не может уменьшаться бесконечно. Процесс закончится. В конце нет соседней инверсии, а значит, ряд возрастает.

Глава

Инварианты II и моноинварианты

Модуль развивает метод инвариантов после базового уровня: чётность, остатки, НОД, произведение знаков, раскраски досок, взвешенные суммы и моноинварианты для доказательства завершения процессов.

Ключевая идея Инвариант — величина или свойство, которое не меняется при разрешённых ходах. Если начальное и конечное состояния имеют разные значения инварианта, переход невозможен. Моноинвариант — величина, которая при каждом ходе строго возрастает или строго убывает. Если она целочисленная и ограничена, процесс обязан закончиться. Основные факты Чаще всего инвариантами бывают чётность, остаток по модулю, сумма, произведение знаков, НОД, раскрасочная сумма. Для досок полезны раскраски: шахматная, по диагоналям, по остаткам координат, с весами \(+1\) и \(-1\). Для процессов ищут величину, которая меняется в одну сторону: число инверсий, сумма квадратов, взвешенная сумма, максимальная высота. Инвариант доказывает невозможность, а моноинвариант чаще доказывает завершение или отсутствие бесконечной игры. Когда применять метод В задаче есть разрешённые операции, ходы, перекрашивания, перестановки, переносы камней. Нужно доказать, что состояние недостижимо. Нужно доказать, что процесс обязательно закончится. В условии есть доска, цвета, остатки, знаки, НОД или повторяющиеся локальные изменения. Как распознать метод Сначала сравните начальное и желаемое состояния: чем они отличаются по чётности, сумме, цветам или остаткам? Затем проверьте, что делает один ход с этой величиной. Если прямой инвариант не виден, попробуйте взвесить клетки или объекты числами. Хорошая весовая функция даёт нулевой вклад для каждого разрешённого хода, но ненулевой вклад для целевого состояния. Типичные ошибки Проверяют инвариант только на одном примере хода, а не на произвольном ходе. Доказывают, что величина не возрастает, но не доказывают строгого изменения; тогда завершение процесса не следует. Используют слишком слабый инвариант: начальное и конечное состояния по нему совпадают. Забывают доказать достаточность, когда задача спрашивает не только невозможность, но и полный критерий достижимости. Мини-чеклист Запишите, что меняет один ход. Проверьте чётность, остатки, сумму, НОД, произведение знаков. Для доски подберите раскраску или веса. Для процесса найдите целочисленную ограниченную величину со строгим изменением. Сравните начальное и конечное состояния по найденной величине.

Пример 1. Чётность числа чёрных монет Простейший инвариант — чётность. Задача. На столе лежат монеты, часть из них чёрной стороной вверх. За ход переворачивают ровно две монеты. Можно ли из положения с одной чёрной монетой получить положение без чёрных монет? Решение. При перевороте двух монет число чёрных монет меняется на \(-2\), \(0\) или \(2\). Во всех случаях его чётность сохраняется. Сначала число чёрных монет нечётно, а в положении без чёрных монет оно равно \(0\), то есть чётно. Поэтому получить такое положение нельзя. Пример 2. Шахматная раскраска Раскраска помогает превратить геометрическую задачу в подсчёт. Задача. Из шахматной доски \(8\times 8\) вырезали две угловые клетки одного цвета. Можно ли покрыть оставшуюся часть домино \(1\times2\)? Решение. Каждое домино покрывает одну чёрную и одну белую клетку. Если вырезаны две клетки одного цвета, то в оставшейся доске чисел чёрных и белых клеток различны. Покрытие домино требовало бы равенства этих чисел. Значит, покрыть доску невозможно. Пример 3. Остатки по модулю Иногда сохраняется не сама величина, а её остаток. Задача. Фишка стоит в точке \(0\) на числовой прямой. За ход её можно сдвинуть на \(6\) вправо или на \(9\) влево. Можно ли попасть в точку \(100\)? Решение. Оба разрешённых сдвига кратны \(3\). Поэтому остаток координаты по модулю \(3\) не меняется. Начальная координата имеет остаток \(0\), а \(100\equiv 1\pmod 3\). Следовательно, попасть в точку \(100\) нельзя. Пример 4. НОД как инвариант При операциях с разностью часто сохраняется НОД. Задача. Есть два положительных числа \(a\) и \(b\). За ход большее число можно заменить разностью большего и меньшего. Докажите, что НОД двух чисел не меняется. Решение. Если \(a\ge b\), то новый набор — \(a-b\) и \(b\). Общие делители \(a\) и \(b\) совпадают с общими делителями \(a-b\) и \(b\): из делимости \(a\) и \(b\) следует делимость \(a-b\), а из делимости \(a-b\) и \(b\) следует делимость \(a\). Поэтому \(\gcd(a,b)=\gcd(a-b,b)\). НОД сохраняется. Пример 5. Сумма квадратов как моноинвариант Для процессов с выравниванием часто работает сумма квадратов. Задача. В двух кучах \(a\) и \(b\) камней, \(a\ge b+2\). Переложили один камень из первой кучи во вторую. Докажите, что сумма квадратов размеров куч уменьшилась. Решение. Сравним старую и новую суммы: \[(a^2+b^2)-((a-1)^2+(b+1)^2)=2(a-b-1).\] Так как \(a\ge b+2\), получаем \(a-b-1\ge 1\). Разность положительна, значит, сумма квадратов строго уменьшилась. Пример 6. Произведение знаков При смене двух знаков произведение всех знаков сохраняется. Задача. На вершинах связного графа стоят знаки \(+\) и \(-\). За ход можно выбрать ребро и поменять знаки в обеих его концах. Докажите, что произведение всех знаков не меняется. Решение. Один ход меняет знак ровно у двух вершин. Значит, произведение всех знаков умножается на \((-1)^2=1\). Следовательно, произведение знаков является инвариантом. Пример 7. Паритет строк и столбцов Иногда один ход сохраняет сразу много чётностей. Задача. На доске \(8\times8\) все клетки белые. За ход выбирают блок \(2\times2\) из соседних клеток и меняют цвет всех четырёх клеток. Докажите, что нельзя получить положение с ровно одной чёрной клеткой. Решение. Один ход меняет две клетки в каждой из двух строк и две клетки в каждом из двух столбцов. Поэтому чётность числа чёрных клеток в каждой строке и каждом столбце сохраняется. В начале все эти чётности равны \(0\). Если чёрная клетка ровно одна, то её строка и её столбец имеют нечётную чётность. Противоречие. Пример 8. Взвешенная сумма для завершения Когда камни двигаются только в одну сторону, полезна взвешенная сумма координат. Задача. В нескольких клетках полоски лежат камни. За ход один камень можно передвинуть на одну клетку вправо, но не дальше \(n\)-й клетки. Докажите, что бесконечная последовательность ходов невозможна. Решение. Рассмотрим сумму номеров клеток, в которых лежат камни, считая каждый камень отдельно. Каждый ход увеличивает эту сумму на \(1\). Сумма не может превышать \(n\) умноженное на число камней. Поэтому она строго возрастает, но ограничена сверху. Бесконечно много ходов невозможно.

Глава

Идеи Рамсея

Модуль вводит идеи вынужденной структуры: раскраски рёбер, одноцветные треугольники, задачи о знакомых и незнакомых, факт \(R(3,3)=6\), рекурсию Рамсея и первые многоцветные оценки.

Ключевая идея Идеи Рамсея говорят: если объект достаточно большой, в нём неизбежно появляется упорядоченная структура. В простейшей форме: при раскраске рёбер полного графа в два цвета найдётся одноцветный треугольник. Метод часто сочетает принцип Дирихле, выбор вершины, разбиение соседей по цветам и индукцию по размеру искомой структуры. Основные факты В любой 2-раскраске рёбер \(K_6\) есть одноцветный треугольник: это факт \(R(3,3)=6\). На \(K_5\) можно раскрасить рёбра в два цвета без одноцветного треугольника: это доказывает, что числа \(5\) недостаточно. Общая рекурсия: \(R(s,t)\le R(s-1,t)+R(s,t-1)\). Доказательства обычно начинаются с одной вершины и анализа цветов рёбер, выходящих из неё. Когда применять метод Нужно доказать, что среди многих объектов найдётся группа с одинаковым отношением. Есть знакомства и незнакомства, красные и синие рёбра, несколько типов связей. В задаче просят гарантировать треугольник, клику, независимое множество, одноцветную цепочку. Нужно найти минимальное число объектов, после которого структура неизбежна. Как распознать метод Если между каждой парой объектов есть один из нескольких вариантов отношения, думайте о полном графе с раскрашенными рёбрами. После выбора вершины разделите остальные вершины на группы по цвету ребра к выбранной вершине. Если одна группа достаточно велика, примените уже известный меньший результат. Типичные ошибки Доказывают только верхнюю оценку и забывают построить пример для нижней оценки. Путают одноцветный треугольник с треугольником, у которого просто есть два ребра одного цвета. В рекурсии Рамсея неверно выбирают размеры групп соседей. В задачах о людях забывают, что отношение должно быть симметричным. Мини-чеклист Переведите условие на язык полного графа с цветными рёбрами. Выберите вершину и посчитайте рёбра каждого цвета из неё. Если группа соседей достаточно велика, ищите структуру внутри этой группы. Для точного ответа проверьте и конструкцию, которая показывает, что меньшего числа недостаточно.

Пример 1. Три ребра одного цвета из вершины Первый шаг почти всех доказательств Рамсея — обычный принцип Дирихле. Задача. Из вершины \(v\) выходит \(5\) рёбер, каждое красное или синее. Докажите, что хотя бы \(3\) из них одного цвета. Решение. Пять рёбер распределены по двум цветам. Если бы каждого цвета было не больше \(2\), всего рёбер было бы не больше \(4\). Противоречие. Значит, рёбер одного цвета хотя бы \(3\). Пример 2. Доказательство \(R(3,3)\le6\) Это главный базовый результат модуля. Задача. Докажите, что при любой красно-синей раскраске рёбер полного графа на \(6\) вершинах есть одноцветный треугольник. Решение. Выберем вершину \(v\). Из неё выходит \(5\) рёбер, поэтому хотя бы \(3\) из них одного цвета, скажем красные, к вершинам \(a,b,c\). Если среди рёбер \(ab,bc,ca\) есть красное, то вместе с \(v\) оно даёт красный треугольник. Если красных среди них нет, то все три ребра синие, и \(a,b,c\) образуют синий треугольник. Пример 3. Почему пяти вершин мало Для точного результата нужна не только гарантия, но и контрпример меньшего размера. Задача. Раскрасьте рёбра \(K_5\) в два цвета так, чтобы не было одноцветного треугольника. Решение. Расположим \(5\) вершин по кругу. Рёбра сторон пятиугольника покрасим в красный цвет, а диагонали — в синий. Красные рёбра образуют цикл длины \(5\), в нём нет треугольника. Синие рёбра тоже образуют цикл длины \(5\), поэтому синего треугольника тоже нет. Пример 4. Язык знакомств Задачи о людях переводятся в раскраску рёбер. Задача. Среди любых \(6\) человек найдутся либо трое попарно знакомых, либо трое попарно незнакомых. Решение. Построим полный граф: вершины — люди, красное ребро означает знакомство, синее — незнакомство. По примеру 2 в этом графе есть одноцветный треугольник. Красный треугольник — трое попарно знакомых, синий — трое попарно незнакомых. Пример 5. Рекурсия Рамсея Большие оценки строятся из меньших. Задача. Объясните, почему \(R(s,t)\le R(s-1,t)+R(s,t-1)\). Решение. Пусть вершин \(R(s-1,t)+R(s,t-1)\). Выберем вершину \(v\). Среди остальных вершин либо красных соседей \(v\) не меньше \(R(s-1,t)\), либо синих соседей не меньше \(R(s,t-1)\). В первом случае внутри красных соседей есть красный \(K_{s-1}\), который вместе с \(v\) даёт красный \(K_s\), или синий \(K_t\). Во втором случае аналогично получаем красный \(K_s\) или синий \(K_t\). Пример 6. Оценка \(R(3,4)\le10\) Это первое применение рекурсии. Задача. Докажите, что среди \(10\) человек найдутся либо \(3\) попарно знакомых, либо \(4\) попарно незнакомых. Решение. Это утверждение соответствует оценке \(R(3,4)\le R(2,4)+R(3,3)\). Имеем \(R(2,4)=4\), потому что красное ребро уже даёт красный \(K_2\), а без красных рёбер \(4\) вершины дают синий \(K_4\). Также \(R(3,3)=6\). Следовательно, \(R(3,4)\le 4+6=10\). Перевод на людей даёт требуемое утверждение. Пример 7. Три цвета и \(17\) вершин Идея Рамсея работает и для большего числа цветов. Задача. Докажите, что при раскраске рёбер \(K_{17}\) в три цвета найдётся одноцветный треугольник. Решение. Выберем вершину \(v\). Из неё выходит \(16\) рёбер трёх цветов, значит, хотя бы \(6\) рёбер одного цвета, скажем красного, идут к множеству \(A\) из \(6\) вершин. Если внутри \(A\) есть красное ребро, оно вместе с \(v\) даёт красный треугольник. Если красных рёбер внутри \(A\) нет, то все рёбра внутри \(A\) раскрашены двумя другими цветами. По \(R(3,3)=6\) внутри \(A\) есть одноцветный треугольник одного из этих двух цветов. Пример 8. Одноцветное связное дерево Не всякая вынужденная структура — клика; иногда гарантируется связность. Задача. Рёбра полного графа покрашены в красный и синий. Докажите, что один из цветовых графов связен. Решение. Если красный граф связен, всё доказано. Если нет, возьмём две разные красные компоненты. Любое ребро между ними не может быть красным, иначе компоненты соединились бы. Значит, все рёбра между разными красными компонентами синие. Тогда синий граф связен: из вершины в одной красной компоненте в вершину другой компоненты есть синее ребро, а внутри одной компоненты можно пройти через любую вершину другой компоненты двумя синими рёбрами.

Глава

Графы II

Модуль развивает графовые методы: степени, деревья, леса, связность, циклы, двудольность, эйлеровы пути, базовые паросочетания и планарные оценки.

Ключевая идея Графы в олимпиадной комбинаторике нужны не ради терминов, а ради перевода задачи на язык вершин, рёбер, степеней, путей, циклов и компонент. Во второй книге важно владеть несколькими леммами: сумма степеней, остовное дерево, дерево как связный граф без циклов, двудольность через нечётные циклы, эйлеровы обходы и простые планарные оценки. Основные факты Сумма степеней равна \(2E\), поэтому число вершин нечётной степени чётно. Связный граф на \(n\) вершинах имеет не меньше \(n-1\) рёбер; дерево имеет ровно \(n-1\) ребро. В дереве между любыми двумя вершинами ровно один простой путь. Граф двудолен тогда и только тогда, когда в нём нет нечётных циклов. Связный граф имеет эйлеров цикл тогда и только тогда, когда все степени чётны. Когда применять метод В задаче есть дороги, знакомства, пары, турниры без направлений, сети, расписания. Нужно доказать существование пути, цикла, компоненты, паросочетания или раскраски. В условии фигурируют степени вершин, чётность числа рёбер, связность или запрет циклов. Конфигурация на плоскости задаёт планарный граф или дерево. Как распознать метод Спросите: что считать вершинами, а что рёбрами? Иногда вершины — это люди, клетки, множества или области, а ребро означает конфликт, соседство, пересечение или возможность перехода. Если граф связен, часто берут остовное дерево. Если есть степени, применяют сумму степеней. Если есть запрет на нечётный цикл, пробуют двудольную раскраску. Типичные ошибки Забывают убрать изолированные вершины при обсуждении эйлерова пути. Считают, что \(E=n-1\) само по себе означает дерево, хотя нужна связность или отсутствие циклов. Путают двудольность с возможностью раскрасить рёбра в два цвета. В планарных задачах применяют формулу Эйлера к несвязному графу без проверки условий. Мини-чеклист Определите вершины и рёбра. Проверьте связность и компоненты. Посчитайте сумму степеней. Если нужен минимум рёбер, ищите дерево; если есть лишнее ребро, ищите цикл. Для обходов проверьте число нечётных степеней.

Пример 1. Сумма степеней Главная формула графов — каждое ребро считается дважды. Задача. Докажите, что сумма степеней всех вершин графа равна удвоенному числу рёбер. Решение. Каждое ребро имеет два конца. При суммировании степеней оно добавляет \(1\) к степени каждого конца, то есть всего \(2\). Поэтому сумма степеней равна \(2E\). Пример 2. Число нечётных степеней Чётность сразу даёт сильный вывод. Задача. Докажите, что в любом графе число вершин нечётной степени чётно. Решение. Сумма всех степеней равна \(2E\), значит, она чётна. Сумма чётных степеней чётна, поэтому сумма нечётных степеней тоже чётна. Это возможно только при чётном количестве нечётных слагаемых. Пример 3. Остовное дерево Связность часто упрощают удалением лишних рёбер. Задача. Докажите, что в любом конечном связном графе есть остовное дерево. Решение. Среди всех связных подграфов, содержащих все вершины, выберем подграф с минимальным числом рёбер. Если в нём есть цикл, удаление одного ребра цикла не нарушит связность, что противоречит минимальности. Значит, циклов нет, и это дерево. Пример 4. Ровно одно лишнее ребро Остовное дерево помогает увидеть циклы. Задача. Связный граф на \(n\) вершинах имеет \(n\) рёбер. Докажите, что в нём ровно один цикл. Решение. Возьмём остовное дерево: в нём \(n-1\) ребро. В исходном графе ровно одно ребро не входит в дерево. Добавление одного ребра к дереву создаёт ровно один цикл. Других циклов быть не может, потому что любой цикл должен использовать это единственное лишнее ребро. Пример 5. Двудольность Двудольность — это раскраска вершин, а не рёбер. Задача. Докажите, что если граф двудолен, то в нём нет нечётного цикла. Решение. В двудольном графе каждое ребро соединяет разные доли. При движении по циклу вершины должны чередовать доли. Чтобы вернуться в исходную долю, нужно сделать чётное число шагов. Значит, любой цикл имеет чётную длину. Пример 6. Эйлеров цикл Условие на степени объясняет, почему можно пройти по всем рёбрам. Задача. Если в связном графе есть замкнутый обход, проходящий по каждому ребру ровно один раз, докажите, что степени всех вершин чётны. Решение. Каждый раз, когда обход входит в вершину, он должен из неё выйти по другому ещё не использованному ребру. Рёбра у вершины разбиваются на пары «вход-выход». Поэтому степень каждой вершины чётна. Пример 7. Максимальное паросочетание Даже до теоремы Холла полезно знать базовую лемму. Задача. В графе выбрано максимальное по включению паросочетание. Докажите, что все рёбра графа имеют хотя бы один конец, покрытый этим паросочетанием. Решение. Если бы существовало ребро, оба конца которого не покрыты, его можно было бы добавить к паросочетанию. Это противоречит максимальности по включению. Пример 8. Планарная оценка Планарность превращает геометрию в подсчёт рёбер и граней. Задача. Докажите, что простой связный планарный граф с \(n\ge3\) вершинами и \(m\) рёбрами удовлетворяет \(m\le3n-6\). Решение. По формуле Эйлера \(n-m+f=2\). Каждая грань ограничена хотя бы тремя рёбрами, а каждое ребро учитывается в границах граней дважды, поэтому \(3f\le2m\). Тогда \(f\le\frac{2m}{3}\), и из формулы Эйлера получаем \(2=n-m+f\le n-m+\frac{2m}{3}=n-\frac{m}{3}\). Значит, \(m\le3n-6\).

Глава

Паросочетания и введение в теорему Холла

Модуль вводит паросочетания, системы различных представителей, условие Холла, регулярные двудольные графы и увеличивающие пути.

Ключевая идея Паросочетание выбирает рёбра без общих концов. В двудольном графе это язык распределения задач, выбора представителей и составления пар. Теорема Холла даёт точный критерий: левую долю \(A\) можно полностью покрыть паросочетанием тогда и только тогда, когда для любого \(S\subseteq A\) множество соседей \(N(S)\) имеет размер хотя бы \(|S|\). Основные факты Необходимость Холла проста: разные вершины из \(S\) должны быть сопоставлены разным соседям из \(N(S)\). Условие Холла проверяется для всех подмножеств, но в задачах его часто доказывают подсчётом рёбер. Если двудольный граф \(d\)-регулярен и доли равны, то в нём есть совершенное паросочетание. Паросочетание не максимально тогда и только тогда, когда существует увеличивающий путь. Когда применять метод Нужно выбрать разные элементы из нескольких множеств. Нужно назначить разные задачи, места, дни, представителей или партнёров. Дан двудольный граф и требуется покрыть одну долю или обе доли. Есть локальные ограничения вида «кому что разрешено». Как распознать метод Если объекты одного типа должны получить попарно разные объекты другого типа, стройте двудольный граф: слева требования, справа возможные выборы. Затем проверьте условие Холла: любая группа требований должна иметь не меньше доступных вариантов, чем её размер. Типичные ошибки Проверяют условие Холла только для одиночных вершин. Путают максимальное паросочетание и совершенное паросочетание. Забывают, что система различных представителей — это паросочетание, покрывающее множества, а не элементы. В регулярном двудольном графе не доказывают равенство размеров долей. Мини-чеклист Определите левую и правую доли. Проведите ребро, если выбор разрешён. Сформулируйте, какую долю надо покрыть. Для произвольного \(S\) оцените \(|N(S)|\). Если паросочетание не максимально, ищите увеличивающий путь.

Пример 1. Что такое паросочетание Паросочетание — набор рёбер без общих концов. В звезде \(K_{1,n}\) любое паросочетание содержит не больше одного ребра, потому что все рёбра имеют общий центр. Пример 2. Необходимость условия Холла Если множество \(S\) левой доли покрыто паросочетанием, то его вершины сопоставлены разным вершинам из \(N(S)\). Поэтому \(|N(S)|\ge |S|\). Пример 3. Система представителей Для множеств \(A_1,\ldots,A_n\) система различных представителей — это выбор \(a_i\in A_i\), причём все \(a_i\) различны. Это паросочетание между множествами слева и элементами справа. Пример 4. Регулярный двудольный граф Если двудольный граф \(d\)-регулярен, то для любого \(S\) слева из \(S\) выходит \(d|S|\) рёбер. Все они входят в \(N(S)\), каждая вершина справа принимает не больше \(d\) таких рёбер, значит, \(d|S|\le d|N(S)|\), и \(|N(S)|\ge |S|\). По Холлу есть паросочетание. Пример 5. Назначение задач Если каждый набор из \(k\) учеников совместно может решать хотя бы \(k\) разных задач, то можно назначить каждому ученику по разной доступной задаче. Это ровно условие Холла. Пример 6. Робастность Если для любого \(S\) выполнено \(|N(S)|\ge |S|+1\), то после удаления любого одного правого объекта всё ещё выполнено \(|N(S)|\ge |S|\), значит, matching сохраняется. Пример 7. Увеличивающий путь Если путь начинается и заканчивается непокрытыми вершинами и его рёбра чередуются: не из паросочетания, из паросочетания, не из паросочетания, то замена вдоль пути увеличивает размер паросочетания на \(1\). Пример 8. Разложение регулярного графа В \(d\)-регулярном двудольном графе можно найти совершенное паросочетание, удалить его, получить \((d-1)\)-регулярный граф и повторять. Так рёбра раскладываются на \(d\) совершенных паросочетаний.

Глава

Производящие функции I

Модуль вводит производящие функции как язык коэффициентов для подсчета сумм, ограниченных композиций, подмножеств с весами, разбиений и рекуррентностей.

Ключевая идея Производящая функция превращает задачу подсчета в задачу о коэффициенте. Если число способов получить сумму \(n\) равно \(a_n\), то мы записываем ряд \(A(x)=a_0+a_1x+a_2x^2+\cdots\). Тогда ответ на вопрос "сколько способов получить \(n\)" - это коэффициент при \(x^n\). Главная сила метода в том, что произведение производящих функций автоматически учитывает независимые выборы. Один множитель описывает один объект или одно ограничение, а произведение описывает все объекты сразу. Основные факты Коэффициент при \(x^n\) обозначают \([x^n]A(x)\). \((1+x)^m\) кодирует выбор подмножества из \(m\) элементов: \(x\) означает "выбрали", \(1\) означает "не выбрали". \(1+x+x^2+\cdots=\frac{1}{1-x}\) кодирует неограниченное число одинаковых предметов. \(1+x+\cdots+x^r\) кодирует выбор числа от \(0\) до \(r\). Произведение \(A(x)B(x)\) соответствует независимому сложению вкладов: коэффициенты сворачиваются по всем разбиениям суммы. Когда применять метод Нужно посчитать решения уравнения вида \(a_1+\cdots+a_k=n\) с ограничениями. Есть выбор подмножеств с заданной суммой весов. Появляется рекуррентность, особенно типа Фибоначчи. Нужно считать разбиения числа, композиции или покрытия полосы. Обычный перебор быстро разрастается, но каждый локальный выбор прост. Как распознать метод Ищите вопрос "какой суммарный вес получился?" Если каждый объект дает небольшой вклад в показатель степени \(x\), то произведение множителей часто сразу строит нужный счет. Еще один признак - фразы "не более", "ровно", "сумма равна", "сколько раз можно взять". Такие ограничения обычно переводятся в конечные или бесконечные геометрические суммы. Типичные ошибки Путают упорядоченные композиции и неупорядоченные разбиения. Используют бесконечный множитель там, где по условию есть верхняя граница. Забывают сдвиг, когда переменная должна быть положительной, а не неотрицательной. Извлекают коэффициент не той степени после замены переменных. Раскрывают длинные произведения вручную вместо того, чтобы использовать симметрию, включения-исключения или рекуррентность. Мини-чеклист Что является вкладом в степень \(x\)? Один выбор независим от другого или порядок важен? Множитель конечный или бесконечный? Какой коэффициент нужно извлечь? Можно ли упростить коэффициент через симметрию, замену \(x\mapsto -x\), рекуррентность или включения-исключения?

Пример 1. Коэффициент как выбор Начинаем с самого важного смысла коэффициента: каждый множитель отвечает за один независимый выбор. Задача. Найдите коэффициент при \(x^3\) в \((1+x)^7\). Решение. При раскрытии \((1+x)^7\) мы выбираем либо \(1\), либо \(x\) из каждого из \(7\) множителей. Чтобы получить \(x^3\), нужно выбрать \(x\) ровно из трех множителей. Это можно сделать \(\binom{7}{3}=35\) способами. Идея. Коэффициент равен числу способов выбрать позиции, из которых пришел множитель \(x\). Пример 2. Неограниченные неотрицательные решения Геометрический ряд кодирует переменную, которая может принимать любые неотрицательные значения. Задача. Сколько решений в неотрицательных целых числах имеет уравнение \(a+b+c=12\)? Решение. Каждая переменная дает множитель \(1+x+x^2+\cdots=\frac{1}{1-x}\). Нужно найти \([x^{12}]\frac{1}{(1-x)^3}\).Из формулы \(\frac{1}{(1-x)^3}=\sum_{n\ge 0}\binom{n+2}{2}x^n\) получаем \(\binom{14}{2}=91\). Идея. Это та же идея, что и метод шаров и перегородок, записанная языком коэффициентов. Пример 3. Верхняя граница Когда переменная ограничена сверху, бесконечный ряд заменяется конечным многочленом. Задача. Сколько решений имеет \(a+b+c=8\), если \(0\le a,b,c\le 3\)? Решение. Нужен коэффициент при \(x^8\) в \((1+x+x^2+x^3)^3\). Удобно считать через дополнение:\((1+x+x^2+x^3)^3=\left(\frac{1-x^4}{1-x}\right)^3\).Без верхней границы решений \(\binom{10}{2}=45\). Если, например, \(a\ge 4\), то после замены \(a'=a-4\) остается \(a'+b+c=4\), то есть \(\binom{6}{2}=15\) решений. Таких переменных три. Если две переменные не меньше \(4\), остается сумма \(0\), и таких случаев \(\binom{3}{2}=3\). Итого \(45-3\cdot 15+3=3\). Идея. Верхняя граница часто приводит к включениям-исключениям. Пример 4. Сумма весов подмножества Произведение \(\prod(1+x^{w_i})\) кодирует выбор или невыбор предметов с весами \(w_i\). Задача. Сколько подмножеств множества \(\{2,3,5,7\}\) имеет сумму элементов \(10\)? Решение. Нужно найти коэффициент при \(x^{10}\) в\[(1+x^2)(1+x^3)(1+x^5)(1+x^7).\]Сумма \(10\) получается двумя способами: \(3+7\) и \(2+3+5\). Значит, коэффициент равен \(2\). Идея. Каждый элемент можно взять не более одного раза, поэтому множитель имеет вид \(1+x^{w_i}\). Пример 5. Рекуррентность Фибоначчи Производящая функция помогает не только считать коэффициент, но и вывести рекуррентность. Задача. Пусть \(t_n\) - число покрытий полоски \(1\times n\) клетками \(1\times 1\) и домино \(1\times 2\). Найдите производящую функцию. Решение. Покрытие либо начинается с одной клетки, после чего остается \(1\times(n-1)\), либо с домино, после чего остается \(1\times(n-2)\). Поэтому \(t_n=t_{n-1}+t_{n-2}\), где \(t_0=1\), \(t_1=1\).Для \(T(x)=\sum_{n\ge 0}t_nx^n\) получаем \(T(x)=1+xT(x)+x^2T(x)\). Значит,\[T(x)=\frac{1}{1-x-x^2}.\] Идея. Сначала строим первый шаг, затем переводим рекуррентность в уравнение для ряда. Пример 6. Фильтр четности Подстановка \(x=1\) считает все коэффициенты, а \(x=-1\) вычитает нечетные степени. Задача. Сколько подмножеств \(n\)-элементного множества имеют четный размер? Решение. Коэффициенты \((1+x)^n\) считают подмножества по размеру. Сумма четных коэффициентов равна\[\frac{(1+1)^n+(1-1)^n}{2}.\]Если \(n\ge 1\), получаем \(2^{n-1}\). Идея. Это первый пример фильтра: мы отделяем нужные степени с помощью специальной подстановки. Пример 7. Различные и нечетные части Иногда производящая функция доказывает равенство двух совсем разных описаний. Задача. Покажите, что число разбиений \(n\) на различные части равно числу разбиений \(n\) на нечетные части. Решение. Различные части кодируются произведением \(\prod_{i\ge 1}(1+x^i)\). Нечетные части кодируются \(\prod_{j\ge 1}\frac{1}{1-x^{2j-1}}\).Теперь\[\prod_{i\ge 1}(1+x^i)=\prod_{i\ge 1}\frac{1-x^{2i}}{1-x^i}=\frac{\prod_{i\ge 1}(1-x^{2i})}{\prod_{i\ge 1}(1-x^i)}=\prod_{j\ge 1}\frac{1}{1-x^{2j-1}}.\]Коэффициенты при \(x^n\) равны, значит, равны и количества разбиений. Идея. Для коэффициента при \(x^n\) фактически нужны только конечные множители до \(i=n\). Пример 8. Переносы в двоичном кодировании В сильных задачах производящая функция может скрывать переносы между разрядами. Задача. Найдите коэффициент при \(x^7\) в \((1+x+x^2+x^3)(1+x^2+x^4+x^6)(1+x^4+x^8+x^{12})\). Решение. Коэффициент считает способы выбрать \(a_0,a_1,a_2\in\{0,1,2,3\}\) так, что \(a_0+2a_1+4a_2=7\).Число \(7\) в двоичной записи равно \(111_2\). Считаем переносы. В младшем разряде \(a_0\) должно быть нечетным: \(a_0=1\) без переноса или \(a_0=3\) с переносом. На каждом следующем разряде состояния без переноса и с переносом снова дают ровно по два перехода, но в конце нужен нулевой перенос. Получается \(4\) способа.Действительно, решения: \((3,2,0)\), \((1,3,0)\), \((3,0,1)\), \((1,1,1)\). Идея. Не раскрывайте произведение полностью: в таких задачах удобнее считать переносы.