|
|
 |
Условие
В таблице n×n разрешается добавить ко всем числам любого несамопересекающегося замкнутого маршрута ладьи по 1. В первоначальной таблице по диагонали стояли единицы, а остальные были нули. Можно ли с помощью нескольких разрешённых преобразований добиться того, что все числа в таблице станут равны? (Считается, что ладья побывала во всех клетках таблицы, через которые проходит её путь.)
Решение
Раскрасим таблицу в шахматном порядке. Любой удовлетворяющий условию маршрут ладьи содержит одинаковое количество белых и чёрных клеток, следовательно, разность между суммой всех "чёрных" чисел и суммой всех "белых" – инвариант. В исходной таблице эта разность не равна нулю, значит, при чётном n добиться равенства нельзя.
Для нечётного n числа сделать равными можно. Докажем это по индукции. База (n = 1) очевидна.
Шаг индукции. Разобьём таблицу на центральный квадрат (n–2)×(n–2) и рамку ширины 1. По предположению индукции можно добиться равенства чисел в центральном квадрате, не затрагивая рамку. Далее прибавим по 1 к числам внутри двух квадратов (n–1)×(n–1), не содержащих угловых единичек (подтаблицу 2×(n–1) можно обойти одним ходом ладьи, а n – 1 чётно). После этого все числа в рамке равны 1, а все числа в центральном квадрате равны между собой. Осталось несколько раз пройти ладьей по рамке.
Ответ
При чётном n нельзя, при нечётном – можно.
Замечания
4 балла
