МОШ 2025, 9 класс, задача 4

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

Решение 1. Пример. Приведём пример раскраски, в которой чёрных клеток. Разобьём квадрат на каёмок и покрасим их в чёрный и белый цвет так, что внешняя каёмка покрашена в чёрный цвет, а соседние каёмки покрашены в разные цвета. На рисунке приведён пример аналогичной раскраски для квадрата . Легко видеть, что эта раскраска удовлетворяет условиям задачи.

Посчитаем количество чёрных клеток. Внешняя чёрная каёмка состоит из клеток, следующая чёрная каёмка — из клеток, следующая — из клеток, , последняя — из клеток. Просуммировав арифметическую прогрессию, получаем чёрных клеток.

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

Назовём ребром общую сторону двух соседних по стороне клеток. В квадрате есть вертикальных рёбер и горизонтальных, всего — рёбер. Будем называть ребро чёрным, если оно разделяет чёрные клетки, белым, если оно разделяет белые клетки, и разноцветным, если оно разделяет чёрную и белую клетки.

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

На границе каждой белой клетки лежит не более двух разноцветных рёбер, а каждое разноцветное ребро лежит на границе ровно одной белой клетки. Из этого следует, что , то есть . Поскольку , то , что и требовалось доказать.

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

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

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

Комментарий 2. Отметим, что в раскрасках, удовлетворяющих условию, связное по стороне множество чёрных клеток не обязательно образует прямоугольную каёмку.