Задача М866‍‍

Решение задачи во всех вариантах основано на таком простом соображении: солдатик, стоящий в центре прямоугольника, не может передвинуться на расстояние, большее чем расстояние между центральной и угловой клеткой. Именно это расстояние $d$‍‍ и служит ответом. Но детали доказательства слегка зависят от чётности чисел $m$‍‍ и $n$‍.‍

Мы будем рассматривать три случая: прямоугольники $2k\times2l$‍,‍ у которых имеются четыре центральные клетки (рис. 1), $(2k+1)\times2l$‍‍ с двумя центральными клетками (рис. 2) и $(2k+1)\times(2l+1)$‍‍ с единственной центральной клеткой (рис. 3). Докажем, что во всех трёх случаях искомое расстояние $d$‍‍ равно $\sqrt{k^{2}+l^{2}}$‍.‍ (С использованием знака $[x]$‍‍ для целой части числа $x$‍‍ ответ в общей задаче в) можно записать так: $$ d=\sqrt{\left[\dfrac{m}{2}\right]^{2}+\left[\dfrac{n}{2}\right]^{2}}.\Big) $$

Таким образом, ответ в обеих задачах а) и б): $d=\sqrt{200}=10\sqrt{2}$‍.‍

Рисунки 1, 2, 3

Чтобы обосновать ответ, мы должны, во-первых, доказать, что при любой перестановке найдётся солдатик, смещающийся на расстояние не более $d$‍,‍ и, во-вторых, привести пример перестановки, при которой любой солдатик смещается на такое (или большее) расстояние.

Первая часть почти очевидна: при любой перестановке центральный солдатик смещается по гипотенузе прямоугольного треугольника, у которого катеты (параллельные сторонам прямоугольника) не превосходят $k$‍‍ и $l$‍,‍ т. е. на расстояние, не большее $d=\sqrt{k^{2}+l^{2}}$‍.‍

Вторая часть — пример перестановки — показана на рисунках 1‍—‍3. В самом простом случае прямоугольник $2k\times2l$‍‍ разрезается на четыре прямоугольника $k\times l$‍‍ и расположенные по диагонали пары прямоугольников (точнее, стоящие в них солдатики) переставляются друг с другом с помощью параллельных переносов. Аналогично, прямоугольник $(2k+1)\times l$‍‍ разрезается на пары переставляющихся прямоугольников $(k+1)\times l$‍‍ и $k\times l$‍.‍ Для прямоугольников $(2k+1)\times(2l+1)$‍‍ солдатик из центральной клетки 1 отправляется в угол 2, солдатик из 2 — в противоположный угол 3, а солдатик из 3 — в центр на место 1 (рис. 3); остальные, — стоящие в двух прямоугольниках $(k+1)\times(l+1)$‍‍ с удалёнными углами и двух других диагональных прямоугольниках $k\times l$‍,‍ — меняются местами, как и в предыдущих вариантах.

Заметим, что если «расстояние» измерять не напрямик, а по числу ходов ладьи (как в условии задачи М883 этого номера), то решение задачи никак не изменится, а ответом будет (в тех же обозначениях) число $d=k+l=\left[\dfrac{m}{2}\right]+\left[\dfrac{n}{2}\right]$‍.‍