ВСОШ 2026, 11 класс, задача 9
( баллов) Даны натуральные числа . В клетчатом квадрате закрашено несколько клеток. В каждой строке и в каждом столбце есть хотя бы одна закрашенная клетка, причём в каждом ряду (строке или столбце) закрашенные клетки идут подряд. Известно, что нет целиком закрашенного квадрата . Какое наибольшее число клеток может быть закрашено?
Ответ
Ответ. .
Решение.
Пример. Закрасим верхние строку и левый столбец. Тогда будет закрашено ровно клеток в соответствии с условием задачи.
Оценка. Пусть закрашенных клеток не меньше, чем . Покажем, что есть полностью закрашенный квадрат . Отметим в каждой строке самых левых закрашенных клеток. Если в какой-то из строк закрашено меньшее число клеток, отмечаем все закрашенные клетки этой строки. Таким образом, отмечено не более закрашенных клеток, причем в первых столбцах отмечены все закрашенные клетки.
Тогда закрашенных, но не отмеченных клеток не меньше, чем
Следовательно, в каком-то из оставшихся столбцов есть хотя бы закрашенных не отмеченных клеток. Выберем в таком столбце верхнюю и нижнюю из таких клеток, обозначим их через и соответственно.
Рассмотрим клетчатый прямоугольник, у которого горизонтальная сторона равна , правая верхняя угловая клетка — клетка , правая нижняя угловая клетка — клетка . Тогда вертикальная сторона такого прямоугольника не меньше, чем . Пусть — его верхняя левая угловая клетка. Тогда лежит в одной строке с клеткой , причём клетка закрашена и не отмечена. Значит, клетка в этой строке левее клетки закрашены, поэтому обязательно закрашена клетка . Аналогично, и нижняя угловая клетка рассмотренного прямоугольника закрашена, следовательно, этот прямоугольник закрашен целиком. Поскольку , мы можем выделить и целиком закрашенный квадрат , что и требовалось.
(A) Ответ и пример закрашенных клеток, удовлетворяющий условию задачи.
(AM) Ошибка в подсчёте ответа. В частности, в качестве ответа указано число, отличающееся от верного ответа на .
(B) Оценка, то есть доказательство, что если закрашены хотя бы клеток, то можно найти закрашенный целиком квадрат .
(B0) Сведение к случаю, когда в каждом ряду закрашена хотя бы клетка.
(B1) Закрашенные клетки разбиты на две группы, отмеченные и неотмеченные, как в приведённом решении.
(BM) Оценка доказывается в предположении, что в каждой строке отмечена ровно клетка, и сведение к этому случаю отсутствует.
(B2) Доказано, что в каком-то столбце есть хотя бы закрашенных неотмеченных клеток, если всего закрашено хотя бы клеток.
(B3) Доказано, что существует полностью закрашенный квадрат , у которого найденный в (B2) столбец — крайний правый.
(B3a) Доказано, что неотмеченные закрашенные клетки в каждой вертикали идут подряд.
(B3b) Утверждение (B3) сформулировано, но не доказано. Например, без доказательства используется (B3a).
Продвижения (B3), (B3a), (B3b) не суммируются. Остальные продвижения и штрафы по оценке суммируются между собой и суммируются с баллами за пример.