Каждая клетка квадрата 100 × 100 покрашена либо в белый, либо в черный цвет. Оказалось, что у каждой белой клетки ровно две соседних с ней по стороне клетки покрашены в белый цвет, а у каждой черной клетки ровно две соседних с ней по стороне клетки покрашены в чёрный цвет. Найдите максимальное возможное количество черных клеток
Решение 1. Пример. Приведем пример раскраски, в которой 5100 черных клеток. Разобьем квадрат на 50 каемок и покрасим их в черный и белый цвет так, что внешняя каемка покрашена в черный цвет, а соседние каемки покрашены в разные цвета. На рисунке приведен пример аналогичной раскраски для квадрата 8 × 8. Легко видеть, что эта раскраска удовлетворяет условиям задачи.
Посчитаем количество черных клеток. Внешняя черная каемка состоит из 99 · 4 клеток, следующая черная каемка — из 95 · 4 клеток, следующая — из 91 · 4 клеток, ..., последняя — из 3 · 4 клеток. Просуммировав арифметическую прогрессию, получаем 5100 черных клеток.
Оценка. Докажем, что в любой раскраске не более 5100 черных клеток. Рассмотрим произвольную раскраску, удовлетворяющую условию. Пусть в ней b чёрных и w белых клеток. Так как все клетки квадрата покрашены, 
Назовем ребром общую сторону двух соседних по стороне клеток. В квадрате 100 × 100 есть 99 · 100 вертикальных рёбер и 99 · 100 горизонтальных, всего 19 800 ребер. Будем называть ребро черным, если оно разделяет черные клетки, бельм, если оно разделяет белые клетки, и разноцветным, если оно разделяет черную и белую клетки.
По условию на границе каждой черной клетки лежат ровно два черных ребра. Но и каждое черное ребро лежит на границе двух черных клеток, поэтому черных ребер ровно b. Аналогично белых ребер ровно w. Поэтому разноцветных ребер
На границе каждой белой клетки лежит не более двух разноцветных ребер, а каждое разноцветное ребро лежит на границе ровно одной белой клетки. Из этого следует, что 
то есть 
Поскольку 
то 
что и требовалось доказать.
Решение 2. Приведtм другой способ сделать оценку. Отметим центры клеток и соединим отрезком центры соседних по стороне разноцветных клеток. Тогда угловые клетки не будут соединены ни с одной другой клеткой, клетки у границы будут соединены ровно с одной клеткой, клетки не у границы будут соединены ровно с двумя клетками. Следовательно, все клетки, кроме угловых, разобьются на цепочки, концы которых лежат на границе, и циклы. На рисунке приведён пример разбиения.
В каждом цикле и в каждой цепочке цвета клеток чередуются, поэтому в цикле количества черных и белых клеток совпадают, а в цепочке — совпадают или отличаются на 1. Всего 
Ответ: 5100 клеток.
Комментарии. Пример оптимальной раскраски единственный. Действительно, из второго решения следует, что черных клеток на 200 больше, чем белых, только в случае, когда все угловые и все конечные клетки цепочек черные. Это соответствует тому, что все граничные клетки черные. Несложно видеть, что такая раскраска только одна.
Отметим, что в раскрасках, удовлетворяющих условию, связное по стороне множество черных клеток не обязательно образует прямоугольную каемку.