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

$2025 \times 2025$ өлшемді тор тақта берілген. Бастапқыда тақтадағы әр бірлік ұяшықтың әр қабырғасы қара түске боялған. Бір жүрісте тақтада бірнеше ұяшықтан тұратын кез келген тіктөртбұрышты таңдап алып, оның барлық қабырғаларын қызыл түске бояуға болады (бір ұяшықтың бір қабырғасын бірнеше рет бояуға рұқсат). Барлық бірлік ұяшықтарының әр қабырғасы қызыл түсті болуы үшін, кемінде неше жүріс жасау керек? ( Зауытхан А. )

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

Ответ: $2025$

Решение:

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

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