Задача 4. Ладьи на доске с дыркой

Что меняет дырка

Без дырки всё просто: две ладьи в одной строке бьют друг друга, поэтому в каждой строке не больше одной ладьи. На доске $360\times 360$ без дырки больше $360$ ладей не поставить.

Дырка помогает поставить больше, ведь сквозь неё ладьи не бьют. Строку, которую пересекает дырка, она режет на два куска — слева от дырки и справа. В каждом куске по-прежнему не больше одной ладьи, а во всей строке — уже до двух. Со столбцами так же.

Пусть дырка занимает $a$ строк и $b$ столбцов. Она не выходит на границы доски, поэтому $a$ и $b$ — от $1$ до $358$. Число ладей обозначим $N$. Нам нужно оценить его сверху — доказать, что при любой дырке $N$ не больше какого-то числа. Такое неравенство $N\le\ldots$ будем называть оценкой.

Оценка по строкам и по столбцам

Строк без дырки $360-a$, в каждой не больше одной ладьи. Строк с дыркой $a$, в каждой не больше двух. Всего

Так же по столбцам:

Для маленькой дырки этого хватает: если $a\le 120$, то уже $N\le 480$. Но для большой дырки оценка слабая: при $a=b=200$ она разрешает $560$ ладей. Нужна ещё одна оценка — такая, что для большой дырки она сильная.

Оценка по полным линиям

Назовём строку или столбец полными, если они не задевают дырку. Полных строк $360-a$, полных столбцов $360-b$. Полные строки и полные столбцы вместе будем называть полными линиями.

Каждая ладья стоит на полной строке или на полном столбце. Действительно, пусть и строка, и столбец ладьи задевают дырку. Дырка — прямоугольник: она занимает все клетки, где её строки встречаются с её столбцами. Значит, ладья стоит в дырке, а там ладей нет.

На полной линии не больше одной ладьи. Дадим каждой ладье её строку, если строка полная, а иначе — её столбец (он тогда полный). Двум ладьям одна линия достаться не может: они стояли бы на одной полной линии и били бы друг друга. Значит, ладей не больше, чем полных линий:

Эта оценка сильная как раз для большой дырки: чем больше дырка, тем меньше полных линий.

Складываем три оценки

По отдельности каждая оценка для какой-то дырки слабая: первые две — для большой, третья — для маленькой. Сложим все три:

Буквы $a$ и $b$ сокращаются: в первые две оценки они входят с плюсом, а в третью — с минусом. Остаётся

Это верно для любой дырки. Больше $480$ не бьющих друг друга ладей поставить нельзя, что и требовалось доказать.

Ровно 480 бывает

Этого задача не спрашивает, но полезно убедиться, что число $480$ уменьшить нельзя. Чтобы поставить $480$ ладей, все три оценки должны разрешать $480$: $360+a\ge 480$, $360+b\ge 480$ и $720-a-b\ge 480$, то есть $a\ge 120$, $b\ge 120$ и $a+b\le 240$. Так бывает только при $a=b=120$. Поставим дырку $120\times 120$ в середину: строки и столбцы с $121$-го по $240$-й.

Пример: в строку дырки номер $120+i$ ставим ладьи в столбцы $i$ и $240+i$, а в столбец дырки номер $120+i$ — в строки $i$ и $240+i$; здесь $i=1,\,2,\,\dots,\,120$. Всего $4\cdot 120=480$ ладей.

Проверим. Ладьи из строк дырки стоят в полных столбцах ($1$–$120$ и $241$–$360$), по одной в каждом. Ладьи из столбцов дырки стоят в полных строках, тоже по одной в каждой. Две ладьи в одной строке дырки разделены дыркой, в одном столбце дырки — тоже. Значит, никакие две ладьи друг друга не бьют.

Второй вариант

Меняется только размер доски: $240$ вместо $360$. Пусть дырка занимает $a$ строк и $b$ столбцов. Те же три подсчёта дают

Складываем:

Доказано: больше $320$ ладей поставить нельзя.

Число $320$ уменьшить нельзя: при дырке $80\times 80$ в середине (строки и столбцы с $81$-го по $160$-й) ставим в строку дырки номер $80+i$ ладьи в столбцы $i$ и $160+i$, а в столбец дырки номер $80+i$ — в строки $i$ и $160+i$ ($i=1,\,\dots,\,80$). Получается $4\cdot 80=320$ ладей, и никакие две не бьют друг друга — проверка та же, что в шаге 5.