ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 98147
Темы:    [ Числовые таблицы и их свойства ]
[ Шахматная раскраска ]
[ Инварианты ]
[ Теория алгоритмов (прочее) ]
Сложность: 4-
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

В таблице  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 балла

Источники и прецеденты использования

олимпиада
Название Турнир городов
Турнир
Дата 1992/1993
Номер 14
вариант
Вариант осенний тур, основной вариант, 8-9 класс
Задача
Номер 1

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .