Какое наименьшее число клеток нужно закрасить в квадрате 7 на 7 чтобы каждая или была закрашенной или граничила с закра

Ответ: 12 клеток.

Привожу решение этой задачи, которое я придумал ещё в 1990 году.
/Очень хочется узнать, удалось ли его кому-нибудь упростить за прошедшие 18 лет :-) /

I. 12 клеток достаточно.
Соответствующая раскраска изображена на рисунке.



II. 11 клеток недостаточно. (Принцип Дирихле. )
Расставим числа, как показано на рисунке:



Какую бы клетку на доске ни закрасили, сумма чисел ней самой и всех соседних с ней клетках не превосходит 6. Поэтому, если закрашено не более 11 клеток, то сумма чисел во всех закрашенных и соседних с ними клетках не превосходит 66. В то же время, сумма ВСЕХ чисел в таблице равна 68 > 66.

Легко видеть, что 10 <= N <= 17
Мне удалось N = 13. Меньше не смог (((

Пример min =12 легко представить, покажу почему нельзя 11(иду со ссылки о решении Вашей новой задачи)
И фото ещё повернул нормально.. .

выделяем квадрат 6x6(стороны кратны трём) , очевидно, что он покрывается четырьмя клетками (и вообще прямоугольник 3Nx3M покрывается N*M клетками) . Остались два объединённых прямоугольника (в виде прямого угла) . прямоугольник 1хN можно покрыть [N / 3] способами (кстати 2xN тоже, [N] означают округление N до ближайшего целого, не меньшего N). Значит первый прямоугольник у нас 1х7, [7/3]=3, а второй всего 1х5(граница с тем прямоугольником уже покрыта) [5/3]=2.
Теперь обобщаем:
Прямоугольник aMxN можно покрыть за [N/3] клеток, где а равно одному, двум или трём.
Итого прямоугольник MxN можно покрыть за [M/3] * [N/3].
Если подставить семёрки, то будет [7/3]*[7/3]=3*3=9.
Проверяйте :) .

24 клетки, по диагонали

Я думаю 24 по диагонали мне так сказали