ВсОШ 2023, 9 класс, задача 3

Ответ. .

Решение. Заметим, что в каждой вертикали и каждой горизонтали стоит ровно по одной ладье.

Покажем сначала, что все ладей не могли попасть в одну часть. Пусть , , , — угловые клетки доски (в порядке обхода против часовой стрелки, см. рис. ). Из симметрии, и должны принадлежать разным частям, как и и . Это значит, что либо и , либо и лежат в одной части, а остальные две клетки — в другой.

Пусть для определённости и лежат в части . Тогда все граничные клетки между ними также должны лежать в части ; действительно, если какая-то такая клетка лежит в части , то в ней же лежит какой-то путь из в , а в части лежит какой-то путь из в ; но эти пути должны иметь общую клетку, что невозможно.

Значит, вся горизонталь между клетками и лежит в части , то есть в ней должна быть хотя бы одна ладья. Аналогично, в части тоже есть целая горизонталь (между и ), а значит, есть ладья. Отсюда и следует требуемое.

Осталось привести пример, когда в одной из частей расположено ладей. Один из возможных примеров устроен так. Рассмотрим диагональ квадрата; в одну часть попадут клетки ниже неё, а также нижняя половина самой диагонали; остальные клетки попадут во вторую часть. Расставим ладью в клетки непосредственно под диагональю; тогда они окажутся в одной части. Оставшуюся ладью поставим в пересечение оставшихся строки и столбца. На рис. указан такой пример при .

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

С использованием этого утверждения оценку можно провести по-разному. Например, из симметрии, есть граничных отрезков доски, принадлежащих одной части, и принадлежащих другой. Из соображения выше, каждые отрезков образуют группу подряд идущих; значит, среди них есть все отрезки какой-то стороны, и мы опять получаем, что в каждой части есть одна из граничных линий (вертикаль или горизонталь).