ВСОШ 2026, региональный этап, 11 класс, задача 9
( баллов) Даны натуральные числа . В клетчатом квадрате закрашено несколько клеток. В каждой строке и в каждом столбце есть хотя бы одна закрашенная клетка, причём в каждом ряду (строке или столбце) закрашенные клетки идут подряд. Известно, что нет целиком закрашенного квадрата . Какое наибольшее число клеток может быть закрашено?
Ответ
Ответ. .
Решение.
Пример. Закрасим верхние строку и левый столбец. Тогда будет закрашено ровно клеток в соответствии с условием задачи.
Оценка. Пусть закрашенных клеток не меньше, чем . Покажем, что есть полностью закрашенный квадрат . Отметим в каждой строке самых левых закрашенных клеток. Если в какой-то из строк закрашено меньшее число клеток, отмечаем все закрашенные клетки этой строки. Таким образом, отмечено не более закрашенных клеток, причем в первых столбцах отмечены все закрашенные клетки.
Тогда закрашенных, но не отмеченных клеток не меньше, чем
Следовательно, в каком-то из оставшихся столбцов есть хотя бы закрашенных не отмеченных клеток. Выберем в таком столбце верхнюю и нижнюю из таких клеток, обозначим их через и соответственно.
Рассмотрим клетчатый прямоугольник, у которого горизонтальная сторона равна , правая верхняя угловая клетка — клетка , правая нижняя угловая клетка — клетка . Тогда вертикальная сторона такого прямоугольника не меньше, чем . Пусть — его верхняя левая угловая клетка. Тогда лежит в одной строке с клеткой , причём клетка закрашена и не отмечена. Значит, клетка в этой строке левее клетки закрашены, поэтому обязательно закрашена клетка . Аналогично, и нижняя угловая клетка рассмотренного прямоугольника закрашена, следовательно, этот прямоугольник закрашен целиком. Поскольку , мы можем выделить и целиком закрашенный квадрат , что и требовалось.