40-я Международная Математическая OлимпиадаРумыния, Бухарест, 1999 год

В квадрате клетчатой бумаги размером $n\times n$ клеток, где $n$ — четное число, отмечены $N$ клеток таким образом, что каждая клетка квадрата (отмеченная или неотмеченная) имеет хотя бы одну отмеченную соседнюю клетку. (Соседними считаются клетки, имеющие общую сторону.) Определите наименьшее возможное значение $N$.

Комментарий/решение

В силу минимальности будем говорить что каждая клетка имеет ровно 1 закрашенную соседнюю клетку. Тогда заметим что закрашенные клетки образуют попарно различные доминошки, и отсюда можно понять что достаточно посчитать минимальное кол-во фигур которые состоят из домино и его соседей, тк за соседними клетками этих фигур тоже не могут стоят за крашеные клетки. Назовем такие фигуры как Anuar.

Раскрасим доску в два цвета так чтобы первый цвет закрашивал все края квадрата и потом так далее чтобы в конце остался квадратик 2 х 2. Закрасим именно первый цвет а второй не будем, тогда в каждой фигуре Anuar ровно 4 за крашеных клетом. Отсюда N равно кол во за крашеных клеток деленый на 4 и по индукции выводим ответ

$N = n/2 * (n/2 + 1)$