Республиканская олимпиада по математике, 2025 год, 9 класс

Дана клетчатая доска размера $2025 \times 2025$. Изначально все стороны всех единичных клеток доски покрашены в чёрный цвет. За один ход можно выбрать любой прямоугольник, состоящий из нескольких клеток доски, и перекрасить все его стороны в красный цвет (одну сторону единичной клетки можно красить несколько раз). Найдите наименьшее число ходов, за которое можно перекрасить все стороны всех единичных клеток доски в красный цвет. ( Зауытхан А. )

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

Ответ: $2025$

Решение:

$Оценка:$ Посмотрим на диагональные клетки. Выделим у них верхние и левые стороны. Легко понять, что таких сторон всего $2025 \cdot 2 = 4050$. также очевидно, что каждый ход, можно закрасить максимум двое из всех сторон. Тогда, чтобы закрасить все $4050$ сторон, требуется как минимум $\frac{4050}{2}=2025$. ходов.

Пример: просто показать пример, где $1$ ходом красите $2025×2025$, потом по $1012$ ходов на вертикали и горизонтали.