Задача 79405

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

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

Условие

За круглым столом сидят n человек. Разрешается любых двух людей, сидящих рядом, поменять местами. Какое наименьшее число таких перестановок необходимо сделать, чтобы в результате каждые два соседа остались бы соседями, но сидели бы в обратном порядке?

Решение

  Пусть t_n — наименьшее число пересаживаний. Докажем, что     при  n ≥ 4.     (1)

  Представим, что участники чаепития сидят в вершинах правильного n-угольника. Тогда их итоговое расположение получается из исходного симметрией относительно некоторой оси. Пусть A – один из участников, наиболее удалённых от оси, B – симметричный ему. Кратчайший путь от A к B по границе многоугольника содержит  k ≥ [^n–1/₂]  сторон, поэтому A должен пройти по пути к B не менее k сторон, то есть сделать не менее k пересаживаний. Но при этих пересаживаниях порядок взаимного расположения остальных  n – 1  участников не меняется и им нужно сделать ещё по меньшей мере t_n–1 пересаживаний между собой, чтобы разместиться в противоположном порядке, откуда и следует (1). Поскольку  t₃ = 1,  из оценки (1) получаем, что
          (2)

          (3)
  Покажем, что знак неравенства в (2) и (3) можно заменить на знак равенства. Занумеруем участников чаепития по порядку от 1 до n и разобьём их на две группы – от 1-го до k-го и от (k+1)-го до n-го. Чтобы поменять порядок в первой группе, пересадим последовательно 1-го участника со 2-м, 3-м, ..., k-м, затем 2-го – с 3-м, 4-м, ..., k-м и т. д. На это уйдёт  (k – 1) + (k – 2) + ... + 1 = ½ (k² – k)  пересаживаний. Аналогично за  ½ (n – k) (n – k – 1)  пересаживаний мы получим обратный порядок во второй группе. Всего нужно  k² – k  пересаживаний при  n = 2k  и k² пересаживаний при  n = 2k + 1.

Ответ

¼ (n² – 2n)  при чётном n;  ¼ (n – 1)²  при нечётном n.

.

Замечания

Идеология. Приведём идею другого вывода оценок. Заметим, что из любых трёх участников чаепития хотя бы двое должны поменяться местами (иначе их порядок сохраняется). Соединим двух участников отрезком, если им ни разу не приходилось пересаживаться друг с другом. Мы получим граф с n вершинами. В силу сделанного замечания рёбра графа не образуют ни одного треугольника. Нетрудно доказать по индукции, что граф с n вершинами без треугольников содержит не более [^n²/₄] рёбер (это частный случай так называемой теоремы Турана; доказательство для чётного n см. в решении задачи М934 а) из Задачника "Кванта"). Следовательно, количество пар участников, которые хотя бы раз пересаживались друг с другом, не меньше
½ n(n – 1) – [^n²/₄],  что совпадает с нашим ответом.

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

журнал
Название	"Квант"
год
Год	1985
выпуск
Номер	11
Задача
Номер	М955
олимпиада
Название	Московская математическая олимпиада
год
Номер	44
Год	1981
вариант
Класс	10
задача
Номер	6