Каждые две из $n$ точек (никакие три из которых не лежат на одной прямой) соединены отрезком, и на всех отрезках расставлены стрелки. Треугольник $ABC$ с вершинами в данных точках называется ориентированным, если стрелки расставлены в направлениях $AB$, $BC$, $CA$ или $AC$, $CB$, $BA$ (например, на рисунке 1 всего три ориентированных треугольника из 10).
Объясните, как расставить стрелки, чтобы не возникло ни одного ориентированного треугольника.
Каково наибольшее возможное число ориентированных треугольников (для каждого $n$)? (Нарисуйте соответствующие примеры для $n=4$, 5 и 6.)
Обозначим данные $n$ точек через $A_1$, $\ldots$, $A_n$.
а) Ответ: надо расставить стрелки по возрастанию номеров точек: от $A_i$ к $A_j$ при $i\lt j$ (см. рис. 1 для $n=5$). Тогда в любом треугольнике из вершины с наименьшим номером выходят две стрелки, поэтому он не ориентирован.
Рис. 1
б) Ответ: наибольшее число ориентированных треугольников равно $\dfrac{n(n^2-1)}{24}$ при нечётном $n$ и $\dfrac{n(n^2-4)}{24}$ при чётном $n$ (см. рис. 2-4 для $n=4$, 5, 6).
Рис. 2Рис. 3Рис. 4
Нам будет удобнее найти наименьшее число неориентированных треугольников, а потом вычесть его из общего числа треугольников, равного $\dfrac{n(n-1)(n-2)}6$ (выбирая последовательно вершины треугольника из данных точек, мы будем иметь для первой вершины $n$ возможностей выбора, для второй — $n-1$, для третьей — $n-2$; при этом каждая тройка вершин в разном порядке будет выбрана 6 раз).
Будем называть пару стрелок (направленных отрезков) согласованной, если они имеют общее начало или общий конец. Очевидно, из трёх пар сторон любого неориентированного треугольника из стрелок ровно две — согласованные (на рисунке 5 — $AB$ и $AC$, $AC$ и $BC$), а любая согласованная пара стрелок принадлежит ровно одному неориентированному треугольнику. Поэтому число неориентированных треугольников равно половине числа согласованных пар. Оценим это число.
Рис. 5
Если из некоторой точки $A$ выходит $k$ стрелок, то число образуемых ими пар равно $\dfrac{k(k-1)}2$. При этом в точку $A$ входит $n-1-k$ стрелок, образующих ещё $\dfrac{(n-1-k)(n-2-k)}2$ согласованных пар. Итак, число согласованных пар с общей вершиной в точке $A$ равно
$$
\dfrac12(k^2-k+(n-1-k)^2-n+1+k)=\dfrac12((n-1)^2-(n-1))-k(n-1-k).
$$
Легко видеть, что наименьшее значение этого выражения достигается при $k=\dfrac{n-1}2$, если $n$ нечётно, и при $k=\dfrac n2$ или $k=\dfrac n2-1$, если $n$ чётно, и равно, соответственно, $\dfrac{(n-1)(n-3)}4$ и $\dfrac{(n-2)^2}4$.
Заметим, что стрелки всегда можно расставить так, чтобы из каждой точки выходило указанное «оптимальное» число стрелок. Действительно, представим, что точки $A_1$, $\ldots$, $A_n$ образуют правильный $n$-угольник и расставим стрелки на его сторонах и диагоналях (не проходящих через его центр) так, чтобы они задавали одно и то же направление обхода центра; на диагоналях, проходящих через центр (они имеются только при чётных $n$) стрелки можно поставить произвольно. Тогда число стрелок, входящих в каждую вершину, отличается от числа стрелок, выходящих из неё, не более чем на 1.
Таким образом, наибольшее число ориентированных треугольников при нечётном $n$ равно
$$
\dfrac{n(n-1)(n-2)}6-\dfrac n2\cdot\dfrac{(n-1)(n-3)}4=\dfrac{n(n^2-1)}{24},
$$
а при чётном $n$
$$
\dfrac{n(n-1)(n-2)}6-\dfrac n2\cdot\dfrac{(n-2)^2}4=\dfrac{n(n^2-4)}{24}.
$$
Приведём набросок другого решения. Пусть $k_i$ — число стрелок, выходящих из точки $A_i$, тогда число неориентированных треугольников равно сумме
$$
\dfrac{k_1(k_1-1)}2+\ldots+\dfrac{k_n(k_n-1)}2=\dfrac{k_1^2+\ldots+k_n^2}2=\dfrac{n(n-1)}4\tag{*}
$$
$\Big($число всех стрелок равно $k_1+\ldots+k_n=\dfrac{n(n-1)}2\Big)$. Если для некоторого расположения стрелок $k_i\ge k_j+2$, для каких-то двух точек, то можно изменить направления (не более чем двух) стрелок так, что $k_i$ уменьшится, а $k_j$ увеличится на 1; при этом сумма квадратов $k_1^2+\ldots+k_n^2$ уменьшится. Следовательно, для «наилучшего» расположения стрелок $|k_i-k_j|\le1$ при всех $i$, $j$, а значит, $k_i=\dfrac{n-1}2$ или $k_i=\dfrac{(n-1)\pm1}2$ (в зависимости от чётности $n$) при всех $i$, откуда с помощью (*) легко получить ответ.
