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

Проект МЦНМО
при участии
школы 57
Задача 30778
Темы:    [ Четность перестановки ]
[ Разложение в произведение транспозиций и циклов ]
[ Четность и нечетность ]
Сложность: 3
Классы: 7,8,9
В корзину
Прислать комментарий

Условие

В ряд выписаны числа 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

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

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