Задача 67452

Темы:    [ Раскраски ] [ Оценка + пример ]

Сложность: 4 Классы: 7,8,9,10,11

Условие

Автор: Заславский А.А.

Каждая клетка квадрата $100\times 100$ покрашена либо в белый, либо в чёрный цвет. Оказалось, что у каждой белой клетки ровно две соседних с ней по стороне клетки покрашены в белый цвет, а у каждой чёрной клетки ровно две соседних с ней по стороне клетки покрашены в чёрный цвет. Найдите максимальное возможное количество чёрных клеток.

Решение 1

Пример. Приведём пример раскраски, в которой $5100$ чёрных клеток. Разобьём квадрат на $50$ «слоёв» толщиной в 1 клетку и покрасим их в чёрный и белый цвет так, что внешний слой покрашен в чёрный цвет, а соседние слои покрашены в разный цвет. На рисунке приведён пример такой раскраски для квадрата $8 \times 8$. Легко видеть, что эта раскраска удовлетворяет условиям задачи.

Посчитаем количество чёрных клеток. Внешний чёрный слой состоит из $99\cdot 4$ клеток, следующий чёрный слой – из $95\cdot 4$ клеток, следующий – из $91\cdot 4$ клеток, $\ldots$, последний – из $3 \cdot 4$ клеток. Просуммировав арифметическую прогрессию, получаем $5100$ чёрных клеток.
Оценка. Докажем, что в любой раскраске не более $5100$ чёрных клеток. Рассмотрим произвольную раскраску, удовлетворяющую условию. Пусть в ней $b$ чёрных и $w$ белых клеток. Так как все клетки квадрата покрашены, то $b + w = 10000$.
Назовём ребром общую сторону двух соседних по стороне клеток. В квадрате $100 \times 100$ есть $99 \cdot 100$ вертикальных рёбер и $99 \cdot 100$ горизонтальных, всего – $19800$ рёбер. Будем называть ребро чёрным, если оно разделяет чёрные клетки, белым, если оно разделяет белые клетки, и разноцветным, если оно разделяет чёрную и белую клетки.
По условию на границе каждой чёрной клетки лежат ровно два чёрных ребра. Но и каждое чёрное ребро лежит на границе двух чёрных клеток, поэтому чёрных рёбер ровно $b$. Аналогично белых рёбер ровно $w$. Поэтому разноцветных рёбер $$19800 - b - w = 19800 - 10000 = 9800.$$ На границе каждой белой клетки лежит не более двух разноцветных рёбер, а каждое разноцветное ребро лежит на границе ровно одной белой клетки. Из этого следует, что $2w \geqslant 9800$, то есть $w \geqslant 4900$. Поскольку $b + w = 10000$, то $b \leqslant 5100$, что и требовалось доказать.

Решение 2

Приведём другой способ сделать оценку. Отметим центры клеток и соединим отрезком центры соседних по стороне клеток разного цвета. Тогда угловые клетки не будут соединены ни с одной другой клеткой, клетки у границы будут соединены ровно с одной клеткой, клетки не у границы будут соединены ровно с двумя клетками. Следовательно, все клетки, кроме угловых, разобьются на цепочки, концы которых лежат на границе, и циклы. На рисунке приведён пример разбиения.

В каждом цикле и в каждой цепочке цвета клеток чередуются, поэтому в цикле количество чёрных и белых клеток совпадает, а в цепочке – совпадает или отличается на 1. Всего цепочек $392/2 = 196$, поэтому максимальная разность между количеством чёрных и белых клеток равна $196 + 4 = 200$. Следовательно, чёрных клеток не больше $5100$.

Ответ

$5100$ клеток.

Замечания

1. Пример оптимальной раскраски единственный. Действительно, из второго решения следует, что чёрных клеток на 200 больше, чем белых, только в случае, когда все угловые и все конечные клетки цепочек чёрные. Это соответствует тому, что все граничные клетки чёрные. Несложно видеть, что такая раскраска только одна.
2. Отметим, что в раскрасках, удовлетворяющих условию, связное по стороне множество чёрных клеток не обязательно образует прямоугольную каёмку (см. рисунок выше).

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Год	2025
Номер	88
класс
Класс	9
задача
Номер	4