ВсОШ 2024, 10 класс, задача 2
Дано нечётное число . В клетчатом квадрате закрашивают клеток. Какое наибольшее количество трёхклеточных уголков можно гарантированно вырезать из незакрашенной клетчатой фигуры? (Г. Шарафетдинова)
Ответ. .
Решение.
Оценка. Разобьём квадрат на квадратиков .
Среди этих квадратиков не более квадратиков, в которых покрашено хотя бы клетки. Остальных квадратиков - не менее штук. Из каждого из них можно вырезать трёхклеточный уголок.
Пример. Построим пример индукцией по нечётным . При закрашенных клеток нет, и можно вырезать один уголок.
Для перехода выделим в квадрате внешнюю "рамку" шириной в две клетки. В этой рамке закрасим все клетки, примыкающие к внутренней границе рамки (см. рис. 4), а в квадрате внутри рамки закрасим клетки по предположению индукции. Общее количество закрашенных клеток равно .
Осталось понять, сколько уголков можно вырезать в этом примере. Любой уголок из непокрашенных клеток целиком лежит либо в рамке, либо во внутреннем квадрате (таких по предположению ). Из рамки же нельзя вырезать более уголков - каждый такой уголок должен содержать хотя бы клетки одного из угловых квадратов , а двух уголков, пересекающихся с одним квадратом, вырезать нельзя. Значит, общее количество уголков не больше .