Задача 105135

Темы:    [ Теория алгоритмов (прочее) ] [ Разложение в произведение транспозиций и циклов ] [ Принцип крайнего (прочее) ]

Сложность: 4- Классы: 9,10,11

Условие

Автор: Шаповалов А.В.

Каждый зритель, купивший билет в первый ряд кинотеатра, занял одно из мест в первом ряду. Оказалось, что все места в первом ряду заняты, но каждый зритель сидит не на своём месте. Билетёр может менять местами соседей, если оба сидят не на своих местах. Всегда ли он может рассадить всех на свои места?

Решение

  Занумеруем места по порядку числами от 1 до n, а зрителей обозначим A₁, ..., A_n – в соответствии с номерами их "законных" мест. Достаточно посадить на свое место несколько последних зрителей так, чтобы ни один из оставшихся не оказался на своем месте (потом мы тот же способ применим к оставшейся части зрителей и т.д.). Назовём зрителя, сидящего на месте, следующем за его "законным", сидящим неудачно.
  Пусть зритель A_n сидит на k-м месте. Рассмотрим два случая.
  1) Каждый из зрителей, сидящих на местах с (k+1)-го до n-го, сидит неудачно. Тогда меняем A_n местами по очереди со всеми последующими. В результате все зрители A_k, ..., A_n окажутся на своих местах.
  2) Среди указанных зрителей есть сидящие удачно. Пусть A_m – ближайший к A_n такой зритель. Тогда меняем A_m по очереди со всеми предыдущими вплоть до An. В результате A_n окажется ближе к своему месту, а зрители, сидевшие (причём неудачно) между A_n и A_m, если они были, "удалятся" от своих мест. Заметим, что при этих пересадках A_m не мог оказаться на своем месте (в первый раз, потому что сидел удачно, а далее он попадает на “законные” места других участвующих в этой “операции” зрителей).
  Повторяя такую операцию мы в конце концов посадим A_n на свое место. (Если при этом будет "реализован" первый случай, то и несколько предыдущих зрителей окажутся на своих местах.)

Ответ

Всегда.

Замечания

5 баллов

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

олимпиада
Название	Московская математическая олимпиада
год
Номер	65
Год	2002
вариант
Класс	10
задача
Номер	4
олимпиада
Название	Московская математическая олимпиада
год
Номер	65
Год	2002
вариант
Класс	11
задача
Номер	3
олимпиада
Название	Турнир городов
Турнир
Дата	2001/2002
Номер	23
вариант
Вариант	весенний тур, основной вариант, 10-11 класс
Задача
Номер	4