Задача
В таблице 10×10 записано 100 различных чисел. За ход можно выбрать любой составленный из клеток прямоугольник и переставить все числа в нём симметрично относительно его центра ("повернуть прямоугольник на 180°"). Всегда ли за 99 ходов можно добиться, чтобы числа возрастали в каждой строке слева направо и в каждом столбце – снизу вверх?
Решение
Покрасим все числа в красный цвет. На каждом ходу будем поворачивать некий красный прямоугольник, после чего перекрашивать одно число в зелёный цвет. Таким образом, зелёные числа больше не будут перемещаться. Будем поддерживать свойства:
1) каждое зелёное число меньше всех красных;
2) в каждой строке слева направо и в каждом столбце снизу вверх сначала идут зелёные числа по возрастанию, а потом – красные числа в произвольном порядке. После 99 таких ходов останется только одно красное число в правом верхнем углу, и требуемое в задаче будет достигнуто.
Изначально свойства выполнены. Пусть перед очередным ходом свойства выполняются и наименьшее из красных чисел – $x$ – стоит в клетке $A$. Будем двигаться вниз от клетки $A$ по красным числам, пока возможно, до клетки $B$. От клетки $B$ – аналогично влево до клетки $C$. Возьмём прямоугольник $ABCD$ (возможно, вырожденный). Он будет красным. Повернём его. Число $x$ окажется в клетке $C$. Числа слева и снизу от него, если есть, – зелёные, и они меньше $x$. Перекрасим $x$. Все свойства, очевидно, выполнены.
Ответ
Всегда.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь