Задание олимпиады: Быстрая окраска клеток в квадрате

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