Задача:
Дан клетчатый прямоугольник 3×11 , на котором отмечены некоторые клетки. Известно, что любой трёхклеточный уголок на этой доске покрывает хотя бы 2 отмеченные клетки. Какое наименьшее количество клеток может быть отмечено?
Ответ:
Для определения минимального количества отмеченных клеток, рассмотрим как образуются трёхклеточные уголки на доске размером 3×11.
Имея 3 ряда и 11 столбцов, у нас есть 20 возможных уголков, которые начинаются в верхнем левом углу каждой клетки (за исключением клеток в самом нижнем ряду и самом правом столбце).
Для минимизации числа отмеченных клеток, мы должны стараться разместить отметки так, чтобы каждый уголок содержал хотя бы две отмеченные клетки, используя как можно меньше отметок.
Рассмотрим следующую стратегию: разместим отметки через одну в верхнем и нижнем ряду. Таким образом, каждый уголок, который начинается в верхнем ряду, будет содержать хотя бы две отмеченные клетки (одну в верхнем ряду и одну в среднем ряду). Аналогично, каждый уголок, который начинается в среднем ряду, будет содержать хотя бы две отмеченные клетки (одну в среднем ряду и одну в нижнем ряду).
При этом, в каждом ряду будет 6 отмеченных клеток (включая крайние клетки).
Таким образом, минимальное количество отмеченных клеток равно 12.