Какое наименьшее количество клеток нужно отметить на доске 9×11, чтобы в любом квадрате 3×3 было хотя бы 4 отмеченных клетки?

Для решения этой задачи можно воспользоваться методом от противного.

Предположим, что нам удастся отметить только 10 клеток на доске 9×11. Тогда в каждом квадрате 3×3 будет отмечено не более 3 клеток.

Рассмотрим центральный квадрат 5×5 на доске 9×11. В нем будет 9 квадратов 3×3. Так как в каждом из них не более 3 отмеченных клеток, то в центральном квадрате 5×5 будет не более 27 отмеченных клеток.

Однако, если в центральном квадрате 5×5 отмечено 10 клеток, то в нем будет хотя бы один квадрат 3×3 с 4 отмеченными клетками.

Таким образом, наименьшее количество клеток, которое нужно отметить на доске 9×11, чтобы в любом квадрате 3×3 было хотя бы 4 отмеченных клетки, равно 11.