При каком наименьшем k можно отметить k клеток доски 9 на 9 так, что при любом размещении на доске трехклеточного уголка он задевает хотя бы две отмеченные клетку?
Решение.
Несложно заметить, что в любом квадрате должно быть отмечено не менее трех клеток, а в каждом прямоугольнике — не менее двух. Поскольку из доски можно вырезать 16 квадратов и 8 прямоугольников всего должно быть от мечено по крайней мере клеток. Пример с 56 от меченными клетками показан н а рисунке.
должно быть отмечено не менее трех клеток, а в каждом прямоугольнике 
— не менее двух. Поскольку из доски 
можно вырезать 16 квадратов 
всего должно быть от мечено по крайней мере 
клеток. Пример с 56 от меченными клетками показан н а рисунке.