Олимпиадная задача по комбинаторике: рассадка жюри у круглого стола, 7-9 класс
Задача
За круглым столом были приготовлены 12 мест для жюри с указанием имени на каждом месте. Николай Николаевич, пришедший первым, по рассеянности сел не на своё, а на следующее по часовой стрелке место. Каждый член жюри, подходивший к столу после этого, занимал своё место или, если оно уже было занято, шёл вокруг стола по часовой стрелке и садился на первое свободное место. Возникшее расположение членов жюри зависит от того, в каком порядке они подходили к столу. Сколько может возникнуть различных способов рассадки жюри?
Решение
Рассмотрим некоторый способ рассадки членов жюри. Назовём члена жюри везучим, если он сидит на своём месте. Первым из невезучих (не считая Николая Николаевича) к столу подошёл тот, чьё место занято Николаем Николаевичем (другой невезучий сел бы на свое ещё свободное место, что противоречит его невезучести). Он занял место следующего (по часовой стрелке) невезучего члена жюри. Вторым из невезучих подошёл тот, чьё место занято первым невезучим (по той же причине), и т.д. Итак, каждый невезучий садится на следущее "невезучее" место за его собственным.
Таким образом, способ рассадки однозначно задаётся способом разбиения жюри на везучих и невезучих.
Николай Николаевич и тот, чьё место он занял, в любом случае являются невезучими. Любой набор членов жюри, не содержащий этих двоих, может быть множеством везучих. Реализовать такой способ рассадки можно, например, так: вслед за Николаем Николаевичем входят все, кого мы выбрали везучими (в любом порядке), а затем все остальные в порядке их рассадки за столом по часовой стрелке. Поэтому количество способов рассадки равно количеству подмножеств множества из 10 человек, то есть 210 = 1024.
Ответ
1024 способа.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь