|
|
 |
Условие
В белом клетчатом квадрате 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. Аналогично и первая ладья не дошла до этих клеток. Противоречие.
