а), б) Ответ: пусть $t_n$ — искомое наименьшее время (в минутах), тогда $t_{2k}=k^2-k$, $t_{2k+1}=k^2$; в частности, $t_4=2$, $t_5=4$, $t_6=6$.
Докажем, что при $n\ge4$
$$
t_n\ge t_{n-1}+\left[\dfrac{n-1}2\right]\tag1
$$
($[a]$ — целая часть числа $a$). Представим, что участники чаепития сидят в вершинах правильного $n$-угольника. Тогда их итоговое расположение получается из исходного симметрией относительно некоторой оси. Пусть $A$ — один из участников, наиболее удалённых от оси, $B$ — симметричный ему. Кратчайший путь от $A$ к $B$ по границе многоугольника (красная ломаная на рисунке 1) содержит $k\ge\left[\dfrac{n-1}2\right]$ сторон (см. рис. 1), поэтому $A$ должен пройти по пути к $B$ не менее $k$ сторон, т. е. сделать не менее $k$ пересаживаний. Но при этих пересаживаниях порядок взаимного расположения остальных $n-1$ участников не меняется и им нужно сделать ещё по меньшей мере $t_{n-1}$ пересаживаний между собой, чтобы разместиться в противоположном порядке, откуда и следует (1).
Рисунок номер 1
Поскольку $t_3=1$ (рис. 2), из оценки (1) получаем, что $$\begin{align*}
t_{2k}&\ge1+\left[\dfrac32\right]+\left[\dfrac42\right]+\ldots+\left[\dfrac{2k-1}2\right]=\\
&\qquad=2(1+2+\ldots+(k-1))=k^2-k,\tag2\\
t_{2k+1}&\ge1+\left[\dfrac32\right]+\ldots+\left[\dfrac{2k-1}2\right]+\left[\dfrac{2k}2\right]=k^2.\tag3
\end{align*}$$
Покажем, что найденного здесь числа пересаживаний достаточно, т. е. знак $\ge$ в (2) и (3) можно заменить на знак $=$. Занумеруем участников чаепития по порядку от $1$ до $n$ и разобьём их на две группы — от $1$-го до $k$-го и от $(k+1)$-го до $n$-го. Чтобы поменять порядок в первой группе, пересадим последовательно $1$-го участника со $2$-м, $3$-м, $\ldots$, $k$-м, затем $2$-го — с $3$-м, $4$-м, $\ldots$, $8$-м и т. д. (рис. 3). На это уйдёт $(k-1)+(k-2)+\ldots+1=\dfrac{k^2-k}2$ пересаживаний. Аналогично, за $\dfrac{(n-k)(n-k-1)}2$ пересаживаний мы получим обратный порядок во второй группе. Всего при $n=2k$ или $n=2k+1$ (т. е. $k=\left[\dfrac{n+1}2\right]$) надо будет произвести $k^2-k$ или $k^2$ пересаживаний, соответственно.
Рисунок номер 2
Рисунок номер 3
Приведём идею другого вывода оценок (2) и (3). Заметим, что из любых трёх участников чаепития хотя бы двое должны поменяться местами (иначе их порядок сохраняется). Соединим двух участников отрезком, если им ни разу не приходилось пересаживаться друг с другом. Мы получим набор отрезков с концами в $n$ точках (или, как говорят, граф с $n$ вершинами). В силу сделанного замечания, эти отрезки (рёбра графа) не образуют ни одного треугольника. Нетрудно доказать по индукции, что граф с $n$ вершинами без треугольников содержит не более $\left[\dfrac{n^2}4\right]$ рёбер (это частный случай так называемой теоремы Турана; доказательство для чётного $n$ было дано в решении задачи М934а в «Кванте» № 11 за 1985 г.). Следовательно, количество пар участников, которые хотя бы раз пересаживались друг с другом, не меньше $\dfrac{n(n-1)}2-\left[\dfrac{n^2}4\right]$, что, как легко проверить, совпадает с правой частью (2) или (3) — в зависимости от чётности $n$.
