|
|
 |
Условие
На клетчатой доске $2n\times 2n$ расставлены $2n$ ладей ($n$ — натуральное число). Докажите, что можно выбрать либо $n$ горизонталей, либо $n$ вертикалей и снять все ладьи с выбранных $n$ рядов так, что оставшиеся ладьи не будут бить друг друга.
Решение 1
Построим граф на ладьях как вершинах, причём соединим рёбрами ладьи, бьющие друг друга. Будем перечислять столбцы и строки, в которых стоят ладьи. Для этого рассмотрим одну из компонент графа, выберем в ней одну из ладей и зафиксируем номер её столбца и номер её строки. Если в компоненте есть другие ладьи, то рассмотрим ладью, которая бьёт выбранную. Если она стоит в том же столбце, то добавим номер её строки, а если в той же строке, то добавим номер её столбца. Затем выберем ладью, которая бьёт одну из уже выбранных, и т.д. На каждом шаге добавляется либо номер столбца, либо номер строки, либо ничего, причём все выписанные строки и столбцы вместе покрывают ладей, которых мы выбрали. Таким образом мы переберём все ладьи данной компоненты, и в списке окажется столбцов и строк вместе максимум на 1 больше, чем ладей в компоненте (так как для первой ладьи мы указали и столбец, и строку).
Проделав то же самое для каждой компоненты, получим список не более чем из $2n+c$ столбцов и строк (возможно, с повторениями), где $c$ — количество компонент. Теперь забудем временно в каждой компоненте про последнюю выбранную ладью. Количество компонент не увеличится. Аналогично сказанному выше получим, что новый список содержит суммарно не больше $(2n-c)+c=2n$ столбцов и строк. Без ограничения общности среди них не больше $n$ столбцов. Если их вычеркнуть, то могут остаться лишь некоторые временно забытые ладьи. Они не бьют друг друга, так как принадлежат разным компонентам.
Решение 2
Если в каком-то столбце стоит больше двух ладей, поставим красную точку в каждой его клетке, где стоит ладья, за исключением двух. Аналогично если в какой-то строке стоит больше двух ладей, поставим синюю точку в каждой её клетке, где стоит ладья, за исключением двух. Без ограничения общности, пусть красных точек не меньше, чем синих.
Назовём столбец пустым, если в нём нет ладей, и плотным, если в нём более одной ладьи. Из равенства количества ладей и количества столбцов получаем, что разность между количеством пустых и плотных столбцов равна количеству красных точек.
Среди столбцов с одной ладьёй выберем максимальное подмножество, в котором все ладьи стоят в разных строках. Эти столбцы назовём удачными, а остальные столбцы с одной ладьёй неудачными. В неудачном столбце ладья стоит в той же строке, что и в каком-то удачном. Без ограничения общности считаем, что в этой строке синяя точка отсутствует в удачном столбце и в одном из неудачных. Тогда разность между количеством неудачных и удачных столбцов не больше количества синих точек. Поэтому она не больше разности между количеством пустых и плотных столбцов. Значит, пустых и удачных столбцов вместе не меньше, чем плотных и неудачных, то есть не меньше $n$. Плотные и неудачные столбцы образуют искомое подмножество (если их меньше $n$, дополнительно вычеркиваем любые столбцы, чтобы вычеркнутых стало ровно $n$).
Решение 3
Предположим противное: для некоторой расстановки ладей это невозможно. Назовём ряд (строку, столбец) густым, если в нём не менее двух ладей, иначе — редким. Назовём густой ряд сильным, если в нём не менее двух ладей на пересечении с редкими рядами, иначе — слабым. Пусть есть $v$ сильных столбцов и $v'$ слабых, $h$ сильных строк и $h'$ слабых. Пусть на пересечении сильных столбцов с редкими строками стоит $k$ ладей, на пересечении сильных строк с редкими столбцами — $m$ ладей, а в объединении слабых строк и слабых столбцов — $c$ ладей. Все эти ладьи различны, поэтому $k + m + c \leqslant 2n$. В слабых столбцах не менее $2v'$ ладей, откуда $c \geqslant 2v'$. Аналогично $c \geqslant 2h'$. Из последних двух неравенств следует, что $c \geqslant v' + h'$.
Отметим ладьи: на пересечении редких рядов, на пересечении слабых строк с редкими столбцами, в каждой сильной строке одну ладью на пересечении с каким-нибудь редким столбцом. Отмеченные ладьи не бьют друг друга. Остальные ладьи стоят в непустых столбцах без отмеченных ладей: $v + v'$ густых столбцов и $m - h$ редких. По предположению $v + v' + m - h > n$. Аналогично $h + h' + k - v > n$. Сложив эти два неравенства, получим $h' + v' + k + m > 2n$. Итак, $2n \geqslant k + m + c \geqslant k + m + v' + h' > 2n$. Противоречие.
Решение 4
Перейдём на язык графов: ряды (строки и столбцы) — это вершины, их число не важно; ладьи — рёбра (ладья «соединяет» строку и столбец, в которых стоит), их $m$ (допустимо нечётное). Будем считать, что вершины-строки — чёрные, а вершины-столбцы — белые, тогда вершины правильно раскрашены в два цвета (могут быть соединены ребром только разноцветные вершины).
Доказываем возможность удаления не более $m/2$ одноцветных вершин, чтобы не осталось проходов (назовём так вершины степени больше 1). Предположим противное.
Посчитаем некоторые вершины первого цвета: $l_1$ — количество листьев (вершин степени 1), соседних с проходами; $p_1$ — количество проходов, все соседи которых проходные; $d_1$ — количество других проходов. Аналогично для второго цвета. У каждого из $d_2$ проходов образуется непустая куча соседних листьев. Всего листьев в кучах $l_1$. Если удалить все проходы первого цвета, а из каждой кучи все листья, кроме одного, то проходов не останется. Тогда, по предположению, $p_1 + d_1 + l_1 - d_2 > m/2$. Аналогично $p_2 + d_2 + l_2 - d_1 > m/2$. Значит, $p_1 + p_2 + l_1 + l_2 > m$.
Концевых рёбер не меньше $l_1 + l_2$. Остальных рёбер не меньше $2p_1$ и не меньше $2p_2$, поэтому не меньше $p_1 + p_2$. Значит, всего рёбер больше $m$, противоречие.
Решение 5
Рассмотрим двудольный граф, вершины которого — строки (одна доля) и столбцы (вторая доля), а рёбрами соединены строка и столбец, если на их пересечении стоит ладья. Выберем наименьшее количество строк и столбцов, покрывающих все ладьи — пусть это будут $a$ строк и $b$ столбцов. Тогда по теореме Кёнига (число рёбер в наибольшем по размеру паросочетании двудольного графа равно числу вершин в его наименьшем по размеру вершинном покрытии) существуют $a+b$ ладей, не бьющих друг друга, назовём их особыми. Из этих ладей не больше $a$ стоят в выбранных строках и не больше $b$ в выбранных столбцах — значит, поскольку особых ладей $a+b$, ровно $a$ в строках и ровно $b$ в столбцах, и эти множества из $a$ и $b$ ладей не пересекаются.
Заметим, что выполняется хотя бы одно из условий (иначе всего ладей больше, чем $2n$):
(1) в $a$ выбранных строках не больше $n+a-b$ ладей вне выбранных столбцов;
(2) в $b$ выбранных столбцах не больше $n+b-a$ ладей вне выбранных строк.
Без ограничения общности, пусть верно (1). Тогда можно выбросить $b$ выбранных столбцов и выбросить оставшиеся неособые ладьи: все они в выбранных строках, и их не более $n-b$ (в частности, $b\leqslant n$), причём мы тратим максимум по столбцу на каждую,
так что всего мы потратим не более $b+(n-b)=n$ столбцов. После этого останутся только особые ладьи, то есть они не бьют друг друга.
