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