|
|
 |
Условие
В ряд выписаны числа 1, 2, 3, ..., n. За один ход разрешается поменять местами любые два числа.
Может ли после 1989 таких операций порядок чисел оказаться исходным?
Решение
Каждая пара (a, b) чисел может находиться в двух состояниях: правильном, когда меньшее число стоит левее, и неправильном, когда меньшее число стоит правее. Если между числами a и b стоит ровно k чисел, и мы поменяем a и b местами, то ровно 2k + 1 пара поменяет свое состояние: сама пара (a, b) и все пары, содержащие одно из чисел a, b и одно из k промежуточных чисел. Поэтому каждая операция меняет четность числа неправильных пар.
В начале все пары были правильными. Значит после 1989 операций число неправильных пар станет нечётным. Следовательно, полученный ряд чисел не совпадает с исходным.
Ответ
Не может.
Замечания
1. Ср. с задачей 30311.
2. Мы фактически воспроизвели доказательство известного факта: транспозиция меняет чётность перестановки. На него, конечно, можно просто сослаться.
Источники и прецеденты использования
| книга | |
| Автор | Генкин С.А., Итенберг И.В., Фомин Д.В. |
| Год издания | 1994 |
| Название | Ленинградские математические кружки |
| Издательство | Киров: "АСА" |
| Издание | 1 |
| глава | |
| Номер | 12 |
| Название | Инвариант |
| Тема | Инварианты |
| задача | |
| Номер | 029 |
