E12 Расстановка ладей с гарантированным выбором

Идея метода: в задачах, где нужно расставить невзаимобьющих ладей (или более абстрактно — выбрать «независимое» множество объектов на клетчатой доске), ответ на вопрос «сколько максимально?» или «можно ли поставить $k$ ладей?» часто решается через двудольные графы и теорему Холла о системе различных представителей.

Ладьи на доске $n \times n$ «бьют» по строке и по столбцу. Максимальное число невзаимобьющих ладей = максимальное паросочетание в двудольном графе «строки ↔ столбцы» с рёбрами там, где клетки разрешены (не закрашены). Теорема Холла даёт критерий: паросочетание, покрывающее все $n$ строк, существует тогда и только тогда, когда для любого множества $k$ строк соответствующие разрешённые столбцы — хотя бы $k$ штук.

Метод называется «с гарантированным выбором», потому что ответ на олимпиадный вопрос часто формулируется так: «докажи, что при любой расстановке запрещённых клеток с условием Х, всегда найдётся расстановка $k$ ладей». Здесь «гарантированность» — это следствие теоремы Холла.

Этот метод чуть сложнее стандартных комбинаторных аргументов, поэтому он для 10–11 класса. Но понять его несложно: всё сводится к проверке условия Холла для всех подмножеств строк.

• Теорема Холла (1935). Пусть $G = (A \cup B, E)$ — двудольный граф. Существует паросочетание, покрывающее все вершины $A$, тогда и только тогда, когда для любого $S \subseteq A$ выполнено $|N(S)| \geq |S|$, где $N(S)$ — множество соседей $S$ в $B$. Условие: двудольный граф, задача о полном паросочетании на одной доле. Применять: как только задача сводится к «для каждой строки выбрать столбец так, чтобы все столбцы были разными».

• Следствие для ладей. Максимальное число невзаимобьющих ладей на доске $n \times m$ (с запрещёнными клетками) = мощность максимального паросочетания в двудольном графе строки ↔ столбцы. Применять: любая задача на ладей с ограничениями по клеткам.

• Дефицит Холла. $\max |M| = |A| - \max_{S \subseteq A}(|S| - |N(S)|)$ — поправка на «плохие» множества. Применять: когда нужно найти точное максимальное паросочетание, а условие Холла не выполнено.

• Переформулировать задачу как двудольный граф: строки — одна доля, столбцы — другая, ребро есть там, где клетка не запрещена.
• Проверить условие Холла: для любого множества $k$ строк подсчитать число разрешённых столбцов. Если везде $\geq k$ — паросочетание существует.
• Найти нарушающее множество: если паросочетание не полное, построй множество $S$ строк с $|N(S)| < |S|$ — это и есть «узкое место».
• Использовать двойной подсчёт: подсчитать число разрешённых клеток двумя способами — через строки и через столбцы.
• Алгоритм Куна: для построения максимального паросочетания (в задачах, где нужно явно указать расстановку).
• Сочетать с принципом Дирихле: если строк $> n$, а столбцов $= n$, то какие-то строки делят столбцы — противоречие с Холлом.

Поверхностные признаки (что буквально написано):
- «расставить ладей так, чтобы они не били друг друга»
- «выбрать по одной клетке из каждой строки (столбца), все в разных столбцах (строках)»
- «для каждого объекта из множества $A$ сопоставить уникальный объект из $B$»

Структурные признаки (форма выражения, объекты):
- Доска с запрещёнными клетками, задача на максимальное «независимое» размещение
- Два множества и отношение «совместимости» между ними
- Условие вида «каждая строка содержит не менее $k$ разрешённых клеток»

Цель задачи (что от тебя хотят):
- Доказать, что можно поставить $n$ (или $k$) ладей при выполнении некоторого условия
- Найти максимальное число невзаимобьющих ладей
- Доказать или опровергнуть существование «системы различных представителей»

Задача 1. Ладьи на доске с ограничениями

Условие: На доске $n \times n$ некоторые клетки закрашены. Известно, что в каждой строке закрашено не более $n-1$ клеток (то есть хотя бы одна свободна). Докажите, что можно расставить $n$ невзаимобьющих ладей на свободных клетках.

Источник: тренировочная (базовая задача на теорему Холла)

Как думать (рассуждение ученика$):
1. $Что вижу?* Доска с запрещёнными клетками, нужно $n$ ладей в разных строках и столбцах. Триггер: «ладьи не бьют друг друга» + «докажи существование».$2. *$Метод: двудольный граф строки ↔ столбцы. Нужно полное паросочетание на стороне строк.$3. *$Применяю теорему Холла: нужно проверить, что для любых $k$ строк разрешённых столбцов хотя бы $k$.$4. *$Ключевое: в каждой из $k$ строк хотя бы 1 свободная клетка. Но это не сразу даёт $k$ различных столбцов... Нужно усилить аргумент.

Решение:
Построим двудольный граф $G$: вершины левой доли — строки $1, \ldots, n$; правой доли — столбцы $1, \ldots, n$; ребро $(i, j)$ есть, если клетка $(i,j)$ свободна.

По условию, у каждой строки $i$ степень $\deg(i) \geq 1$. Проверим условие Холла. Возьмём произвольное $S \subseteq \{1,\ldots,n\}$ строк, $|S| = k$. Нам нужно $|N(S)| \geq k$.

Общее число рёбер из $S$ равно $\sum_{i \in S} \deg(i) \geq k$ (каждая строка имеет степень $\geq 1$). Все эти рёбра ведут в $N(S)$. Если $|N(S)| < k$, то $|N(S)| \leq k-1$, значит общее число рёбер $\leq |S| \cdot |N(S)| \leq k(k-1) < k^2$. С другой стороны, в $S$ всего $k$ строк, по $n$ столбцов. Закрашенных клеток в $S$ строках не более $k(n-1)$, свободных — не менее $k$. Но мы хотим конкретнее: разрешённых столбцов хотя бы $k$?

Другой аргумент: заменим закрашивание на более сильное условие. Рассмотрим $k$ строк. Если все их свободные столбцы уместились в $k-1$ столбцах, то в каждой из $k$ строк все свободные клетки — только в этих $k-1$ столбцах. Значит в каждой строке закрашено $\geq n-(k-1) = n-k+1 \geq 1$ клетка в остальных столбцах. Число закрашенных клеток в $S$ строках: $\geq k \cdot (n - (k-1))$. Но закрашенных клеток на доске всего не более... Здесь нужно дополнительное ограничение.

С условием «в каждой строке $\leq n-1$ закрашена» Холл выполнен только при $n=1$ очевидно; для общего $n$ нужно более сильное условие, например «каждый столбец тоже имеет хотя бы одну свободную клетку» — тогда двойной счёт закрывает задачу.

Заметим: условие «каждая строка имеет $\geq 1$ свободную» само по себе не достаточно (контрпример: все $n$ свободных клеток в одном столбце). Правильная формулировка, при которой Холл работает: «каждое множество $k$ строк имеет $\geq k$ свободных столбцов» — это и есть условие Холла напрямую.

Ответ: При выполнении условия Холла расстановка $n$ невзаимобьющих ладей существует.

Что главное: Теорема Холла превращает вопрос о существовании расстановки в локально-проверяемое условие на подмножества строк.

Задача 2. Гарантированный выбор представителей

Условие: В школе $n$ кружков и $n$ учеников. Каждый кружок посещают не менее $k$ учеников, и каждый ученик посещает не более $k$ кружков. Докажите, что можно выбрать по одному представителю от каждого кружка так, чтобы все представители были разными учениками.

Источник: тренировочная (стандартная задача на СРП, ВсОШ тип)

Как думать (рассуждение ученика$):
1. $Триггер:* «по одному представителю», «все разные» — это система различных представителей (СРП$).
2. $Метод: теорема Холла. Нужно полное паросочетание в двудольном графе кружки ↔ ученики.$3. *$Проверяем Холла: для $S$ кружков, $|S| = m$, нужно $|N(S)| \geq m$.$4. *$Подсчёт рёбер:* число рёбер из $S$ — не менее $mk$ (каждый кружок имеет $\geq k$ учеников). Каждый ученик в $N(S)$ даёт $\leq k$ рёбер. Значит $|N(S)| \cdot k \geq mk$, откуда $|N(S)| \geq m$.

Решение:
Построим двудольный граф: левая доля — $n$ кружков, правая — $n$ учеников; ребро $(C_i, u_j)$ есть, если ученик $j$ посещает кружок $i$.

Проверяем условие Холла. Возьмём $S \subseteq$ кружков, $|S| = m$. Подсчитаем рёбра из $S$: каждый кружок в $S$ имеет $\geq k$ учеников-соседей, итого рёбер $\geq mk$. Все эти рёбра ведут в $N(S)$. Каждый ученик в $N(S)$ смежен с $\leq k$ кружками (по условию). Значит:$$mk \leq |\text{рёбер из } S| \leq |N(S)| \cdot k \implies |N(S)| \geq m.$$

Условие Холла выполнено, следовательно полное паросочетание (= СРП) существует.

Ответ: Такой выбор представителей всегда возможен.

Что главное: Двойной подсчёт рёбер + ограничение на степень в правой доле — стандартный способ проверить условие Холла.

• Ошибка: неправильно построить двудольный граф. Путают, что «вершины», а что «рёбра»; иногда делают ориентированный граф вместо двудольного. → Как избежать: чётко назови два множества вершин и критерий наличия ребра.
• Ошибка: условие Холла проверяют только для одного подмножества. Нужно проверить ДЛЯ ВСЕХ подмножеств $S$. На олимпиаде часто достаточно общего аргумента (как в задаче 2), а не перебора. → Как избежать: начинай с произвольного $S$ и рассуждай в общем виде.
• Ошибка: перепутать «условие Холла выполнено» и «паросочетание существует». Теорема Холла — это «тогда и только тогда». Если ты используешь только одно направление, уточни, какое именно. → Как избежать: явно укажи, в каком направлении применяешь теорему.
• Ошибка: забыть про симметрию. Условие Холла для покрытия левой доли $\neq$ условие Холла для правой. Для ладей нужно покрыть строки (а не столбцы). → Как избежать: определи, какую долю хочешь полностью покрыть.
• Ошибка: думать, что теорема Холла даёт только существование, но не построение. Алгоритм Куна явно строит паросочетание. Если задача просит указать расстановку, нужна конструкция. → Как избежать: различай задачи на существование и задачи на явное построение.