Для решения задачи необходимо наблюдать за структурой уголков в клетчатом прямоугольнике. Рассмотрим возможные типы уголков, которые могут быть на доске. Тип 1: трехклеточный уголок заполнен полностью.

XXX

XXX

XXX

Этот тип уголка покрывает 9 клеток. Тип 2: трехклеточный уголок заполнен частично.

XXX

.X.

...

Этот тип уголка покрывает 5 клеток. (В данном случае отмечены три клетки, но необходимо учитывать, что любой уголок покрывает как минимум две отмеченные клетки.) Тип 3: трехклеточный уголок не заполнен, но содержит отмеченные клетки.

X..

.X.

...

Этот тип уголка покрывает 2 клетки. Таким образом, чтобы углок покрывал хотя бы две отмеченные клетки, он может быть только типа 1 или 2. Уголков типа 3 быть не может, так как они не покрывают две отмеченные клетки. Поступим следующим образом: 1. Заполним доску уголками типа 1, тем самым покрыв все клетки (9 клеток). 2. Удалим два уголка типа 1, чтобы была возможность заменить их уголками типа 2. 3. Заменим удаленные уголки типа 1 на уголки типа 2, покрывающие 5 клеток каждый (10 клеток). Таким образом, наименьшее количество отмеченных клеток равно 10.