Раскраски

В решении будем называть квадратами все четверки с координатами Аналогичное определение введем для квадратов

Пример. Покрасим две соседние диагонали в черный цвет, в обеих диагоналях по клеток, так как нумерация циклическая, затем две диагонали пропустим, далее снова красим две диагонали в черный цвет и т.д. В конце ровно половина всех клеток будет покрашена в черный цвет. Возьмем все квадраты у которых левая нижняя клетка черная, и пусть за каждым из них наблюдает спутник. Для квадратов с левыми нижними углами в “нижней” черной диагональю уникальными клетками будут как раз эти углы, а для квадратов с левыми нижними углами на “верхней” черной диагонали уникальными клетками будут их правые верхние углы. Понятно, что всего выбранных квадратов ровно половина от общего количества.

Оценка. Обозначим количество спутников через Отметим для каждого спутника любую из его уникальных клеток и рассмотрим все вертикальные доминошки, содержащие эти клетки. Заметим, что из них принадлежат ровно одному квадрату соответствующему некоторому спутнику. Докажем, что есть хотя бы вертикальных доминошек, не лежащих целиком ни в каком квадрате для некоторого спутника. Для каждой из отмеченных клеток есть хотя бы одна такая доминошка, покрывающая эту клетку. И каждую такую доминошку мы посчитали не более раз, так как в ней всего клетки. Всего вертикальных доминошек То есть у нас есть не больше вертикальных доминошек, лежащих в двух квадратах и доминошек, лежащих ровно в одном квадрате. При этом в каждом квадрате лежат ровно доминошки. Тогда всего квадратов соответствующих спутникам, не больше

откуда то есть