Комбинаторика на Иннополисе

Для начала заметим, что если у нас есть какая-то закрашенная клетка, то сама по себе она не является соседней по стороне.Значит, одна из четырех (или меньшего количества) клеток тоже должна быть закрашена. Получается, у каждой клетки должна быть закрашена соседняя по стороне клетка, в том числе и у закрашенных.

Оценка. Давайте рассмотрим пары отмеченных клеток:

Заметим, что чтобы для каждой из пар клеток выполнялось условие, хотя бы две из пяти клеток (соседних 3 или сами 2 рассматриваемые клетки) должны быть закрашены. Причём области, где могут находиться закрашенные клетки с каждой из пар отмеченных клеток не пересекаются. Значит, наименьшее количество клеток, которые можно закрасить, чтобы выполнялось условие - 2016.

Пример. Закрасим центральную строку:

Тогда у каждой клетки найдётся соседняя по стороне закрашенная клетка.