РЕШУ ОЛИМП — математика

Задания

Назовем клетчатым квадрантом четверть плоскости, расположенную выше оси X и правее оси Y, разбитую на клеточки со стороной 1. В клетчатом квадранте закрашены n² клеток. Докажите, что в этом квадранте найдется не менее n² + n клеток (в том числе, закрашенных), соседних по стороне с хотя бы одной закрашенной.

(С. Берлов, Д. Ширяев)

Решение. Будем доказывать чуть более общее утверждение. Пусть в бесконечном клетчатом квадранте закрашено $a больше или равно n в квадрате$ клеток. Тогда у закрашенньх клеток будет как минимум $a плюс n$ соседей. Используем индукцию по n. Базу удобнее всего проверить при $n минус 0:$ соседей всегда не меньше, чем самих закрашенных клеток (поскольку у каждой закраненной клетки есть сосед справа и все эти соседи различны).

Для перехода используем для идеи. Они обе просты и незатейливы, но мало связаны друг с другом.

Идея 1. Разобьем весь квадрант на вертикальные полосы ширины 2. Заметим, что в каждой такой полосе, в которой есть хотя бы одна закрашенная клетка (будем называть такие полосы непустыми), соседей хотя бы на одного больше, чем закрашенных клеток. В самом деле, в каждой горизонтальной доминошке (из которых сложена эта полоса) соседей всегда ровно столько жсе, сколько закрашенных клеток  — проверьте это! Кроме того, самая верхняя закрашенная клетка в полосе даёт еще одного «лишнего» соседа  — сверху от себя.

Таким образом, если среди полос ширины 2 есть хотя бы n непустых, то соседей окажется хотя бы на n больше, чем закрашенных клеток, что и требовалось (и без всякой индукции).

Идея 2. Все клетки квадранта разбиваются на диагональные ряды (в самом первом ряду всего одна клетка, в следующем  — две, и т. д.). Рассмотрим самую верхнюю диагональ, в которой еть хотя бы одна закрашенная клетка. Все закрашенные клетки в этой диагонали разбиваются на блоки подряд идущих. Рассмотрим один из таких блоков; пусть в нём k закрашенных клеток.

В следующей (более длинной) диагонали есть $k плюс 1$ клеток, соседних с клетками этого блока. Заметим, что других закрашенных соседей у них нет; здесь используется, что соседние в нашей диагонали с рассматриваемым блоком клетки не закрашены (или вообще находятся за границей квадранта). Поэтому, если выкинуть k клеток этого блока (перестать считать их закрашенными), исчезнет $k плюс 1$ соседей. И если окажется, что соседей осталось хотя бы на $n минус 1$ больше, чем закрашенных клеток, то на исходной картинке их было хотя бы на n больше.

Осталось разобрать два случая. Если $k больше или равно 2 n,$ то клетки нашего диагонального блока затрагивают хотя n полос ширины 2, а значит, работает идея $1 .$ Если же $k меньше или равно 2 n минус 1,$ то после выкидывания этого блока останется

$a минус k больше или равно n в квадрате минус 2 n плюс 1= левая круглая скобка n минус 1 правая круглая скобка в квадрате ,$

и по индукционному предположению соседей осталось хотя бы на $n минус 1$ больше, чем закрашенных клеток.

Ключ