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