Построим прямоугольник 3×9: +---+---+---+---+---+---+---+---+---+ | | | | | | | | | | +---+---+---+---+---+---+---+---+---+ | | | | | | | | | | +---+---+---+---+---+---+---+---+---+ | | | | | | | | | | +---+---+---+---+---+---+---+---+---+ Обозначим отмеченные клетки как "1", а пустые как "0". Тогда наша задача - найти такое распределение единиц и нулей в этом прямоугольнике, при котором любой трёхклеточный уголок будет покрывать хотя бы 2 отмеченные клетки, и при этом количество отмеченных клеток будет минимальным. Предположим, что мы можем разместить только 2 отмеченные клетки на прямоугольнике. Такое распределение может быть следующим: +---+---+---+---+---+---+---+---+---+ | | | | | | | | | 1 | +---+---+---+---+---+---+---+---+---+ | | | | | | 1 | | | | +---+---+---+---+---+---+---+---+---+ | | | | | | | | | | +---+---+---+---+---+---+---+---+---+ Однако в этом случае можно легко найти трёхклеточный уголок, который будет покрывать только 1 отмеченную клетку. Например, возьмём верхний левый уголок: +---+---+---+---+---+---+---+---+---+ | 1 | | | | | | | | | +---+---+---+---+---+---+---+---+---+ | 1 | | | | | 1 | | | | +---+---+---+---+---+---+---+---+---+ | | | | | | | | | | +---+---+---+---+---+---+---+---+---+ Таким образом, распределение с двумя отмеченными клетками не будет удовлетворять условию задачи. Рассмотрим теперь распределение с тремя отмеченными клетками: +---+---+---+---+---+---+---+---+---+ | 1 | | | | | | | | | +---+---+---+---+---+---+---+---+---+ | 1 | | | | | | | | | +---+---+---+---+---+---+---+---+---+ | | | 1 | | | | | | | +---+---+---+---+---+---+---+---+---+ Теперь любой трёхклеточный уголок будет покрывать как минимум 2 отмеченные клетки. Можно проверить, что невозможно найти трёхклеточный уголок, покрывающий только 1 отмеченную клетку. Таким образом, наименьшее количество отмеченных клеток - 3.