Дана таблица 7 на 7, некоторые клетки которой закрашены таким образом, что в любом квадрате в этой таблице закрашенных клеток меньше половины. Какое наибольшее количество клеток может быть закрашено во всей таблице?

Пусть некоторые клетки закрашены, причем для каждого квадрата 3×3 (а таких квадратов в таблице 7×7 ровно 25) число закрашенных клеток меньше половины от 9, то есть оно не может быть 5 и более (так как 4 < 4.5, а 5 уже не меньше 4.5). Значит в любом 3×3 квадрате максимум может быть 4 закрашенные клетки.

Основная идея состоит в том, чтобы посчитать, сколько раз каждая клетка участвует в различных 3×3 квадратах, и затем использовать двойное пересчет для получения неравенства. Если каждой закрашенной клетке приписать «вес» – число тех 3×3 квадратов, в которых она входит, то сумм...