Обозначим членов компании точками на плоскости (никакие три из которых не лежат на одной прямой). Тот факт, что $A$ нравится $B$, будем обозначать отрезком со стрелкой, направленным от точки $A$ к точке $B$. Тогда из каждой точки будет выходить ровно $k$ стрелок, а всего $kn$ стрелок. Нам нужно найти число $k_0$ — наименьшее значение $k$, при котором обязательно хоть на одном отрезке будут поставлены стрелки в обе стороны.
Всего существует $\dfrac{n(n-1)}2$ отрезков без стрелок, соединяющих $n$ точек. Если на каждом отрезке не более одной стрелки, то стрелок не больше, чем $\dfrac{n(n-1)}2$. Значит, если $kn\gt\frac{n(n-1)}2$, то $k\ge k_0$. Отсюда
$$
k_0 \le
\begin{cases}
\dfrac{n}2,&\text{если}~n~\text{чётное,}\\[9pt]
\dfrac{n+1}2,&\text{если}~n~\text{нечётное.}
\end{cases}
\tag{1}
$$
Докажем, что неравенство (1) можно заменить на равенство. Поставим в формуле (1) знак равенства и покажем, что $n$ точек при любом $n$ можно так соединить отрезками со стрелками, что из каждой выходит ровно $k_0-1$ стрелок, и ни на одном отрезке нет двух стрелок. Вот один из способов сделать это. Надо $n$ точек расположить в вершинах правильного $n$-угольника и из каждой точки направить стрелки в $k_0-1$ вершин, следующих за ней по часовой стрелке. Поскольку $k_0-1\lt\dfrac n2$ при всех $n$, то никакие две стрелки не окажутся на одном отрезке.
