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

Проект МЦНМО
при участии
школы 57
Задача 66628
Тема:    [ Инварианты ]
Сложность: 2+
Классы: 6,7,8
В корзину
Прислать комментарий

Условие

Автор: Фольклор

У Ильи есть табличка $3\times 3$, заполненная числами от $1$ до $9$ так, как в таблице слева. За один ход Илья может поменять местами любые две строчки или любые два столбца. Может ли он за несколько ходов получить таблицу справа?

1 2 3
4 5 6
7 8 9
1 4 7
2 5 8
3 6 9


Решение

Заметим, что как при перемене двух строк местами, так и при перемене двух столбцов местами числа 1 и 2 остаются в одной строке. Во второй таблице это не так, поэтому получить её Илье не удастся.

Ответ

Нет, не может.

Замечания

Можно заметить, что при описанных действиях наборы чисел в строках и столбцах не меняются, т.е. в какой-то строке всегда в некотором порядке будут числа 1, 2, 3, в другой — 4, 5, 6, в третьей — 7, 8, 9. Величина (обычно, числовая, но бывает и иначе), которая не меняется в ходе некоторого процесса, называется инвариантом.

Про инварианты можно почитать, например, в статье Ю. Ионина, Л. Курляндчика “Поиск инварианта” (журнал Квант, 1976 г., № 2).

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

олимпиада
Название Турнир им.Ломоносова
номер/год
Год 2019
задача
Номер 3

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

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