Европейская математическая олимпиада среди девочек (EGMO). 2026 год. Франция

Клетчатая доска $2026 \times 2026$ называется бордосской, если по крайней мере одна из её $2026^2$ клеток покрашена в красный цвет. Клетчатый прямоугольник назовём нечётным прямоугольником, если он содержит нечётное число красных клеток. Определите наибольшее натуральное число $M$ такое, что любая бордосская доска $2026 \times 2026$ содержит нечётный прямоугольник, в котором минимум $M$ клеток.
   Замечание: Клетчатый прямоугольник — это прямоугольник, состоящий из клеток доски. Эти прямоугольники содержат все свои внутренние клетки.

Комментарий/решение

Ответ: $1013^2$

Оценка: Рассмотрим доску где покрашены $4$ центральные клетки, тогда очевидно что больше $1013^2$ быть не может.

Пример: Пусть $\exists$ доска где в любом прямоугольнике в котором не меньше $1013^2$ клеток четное количество красных клеток. Такие прямоугольники будем называть фархадами

Тогда рассмотрев разницу между квадратами $1013^2$ и $1014^2$ , видим что любой прямоугольник $1 \times 1013$ - фархад. Тогда поделим доску $2026 \times 2026$ на $4$ квадратика $1013 \times 1013$ и рассмотрим клетку $A$ - самую правую и одновременно самую нижнию красную клетку в левом - верхнем квадратике $1013 \times 1013$ , и рассмотрев прямоугольник где левая верхняя угловая клетка это $A$ видим что этот прямоугольник нечетный , так как правый нижний квадратик $1013 \times 1013$ и прямоугольник $1 \times 1013$ - фархады. Откуда получаем противоречие , значит всегда $\exists$ нечетная доска в которой не менее $1013 \times 1013$ клеток.

почему прямоугольники голубые