|
|
 |
Условие
В белом клетчатом квадрате 2021×2021 требуется закрасить чёрным две клетки. После этого через каждую минуту одновременно закрашиваются чёрным все клетки, которые граничат по стороне хоть с одной из уже закрашенных. Ваня выбрал две начальные клетки так, чтобы весь квадрат закрасился как можно быстрее. Через сколько минут закрасился квадрат?
Решение
Занумеруем строки и столбцы числами от –1010 до 1010. Через $n$ минут будут закрашены клетки, до которых хромая ладья (за ход сдвигается на соседнюю клетку) дойдёт от одной из исходных клеток не более чем за $n$ ходов.
Пример. Закрасим клетки $A$(–505, 0) и $B$(505, 0). За 1515 ходов ладья дойдёт из $B$ до любой клетки правой половины доски (клетки ($x, y$) с неотрицательным $x$): потребуется не более 505 ходов по горизонтали и не более 1010 по вертикали. Аналогично из $A$ ладья дойдёт до любой клетки левой половины.
Оценка. Назовём расстоянием между клетками сумму расстояний между ними по вертикали и по горизонтали. Оно равно минимальному числу ходов, за которое хромая ладья сможет дойти из одной клетки в другую (и поэтому удовлетворяет неравенству треугольника). Пусть все клетки будут чёрными через 1514 минут. Противоположные угловые клетки не могут быть "обслужены" одной ладьёй: расстояние между ними больше чем 2·1514. Поэтому каждая ладья "обслужила" две угловые клетки с одной стороны, например ладья из клетки $A$ – обе левые: (–1010, ±1010), а ладья из клетки $B$ – обе правые: (1010, ±1010). Но тогда вторая ладья не успела дойти ни до одной из клеток (0, ±1010): расстояние от такой клетки до противоположной угловой клетки равно 3030 > 2·1514. Аналогично и первая ладья не дошла до этих клеток. Противоречие.
Ответ
Через 1515 минут.
Замечания
6 баллов
