, 2016

Answer: $\frac{n(n^2-1)}{24}$ if $n$ is odd and $\frac{n(n^2-4)}{24}$ if $n$ is even.

Let $a_i$ be the number of students that student $i$ loves ($1 \le i \le n$). Then the number of love triangles is
$$T = \binom{n}{3} - \binom{a_1}{2} - \dots - \binom{a_n}{2}.$$
This is explained as follows. In a non-love triangle $ABC$, one student, say $A$, loves $B$ and $C$, while $B$ loves $C$. For each pair $B$, $C$ of students that $A$ loves, one triangle is thus deducted above from the total number of triangles.

Simplifying the above expression, we get
$$T = \binom{n}{3} + \frac{1}{2}(a_1 + \dots + a_n) - \frac{1}{2}(a_1^2 + \dots + a_n^2).$$
We have $\binom{n}{3} = \frac{n(n-1)(n-2)}{6}$ and $a_1 + \dots + a_n = \binom{n}{2} = \frac{n(n-1)}{2}$, while the sum of squares is bounded by Chebyshev's Inequality:
$$\frac{a_1^2 + \dots + a_n^2}{n} \ge \left( \frac{a_1 + \dots + a_n}{n} \right)^2 = \frac{1}{n^2} \binom{n}{2}^2 = \frac{(n-1)^2}{4},$$
yielding
$$a_1^2 + \dots + a_n^2 \ge \frac{n(n-1)^2}{4}.$$

Hence an upper bound for the number of love triangles is given by
$$T \le \frac{n(n-1)(n-2)}{6} + \frac{1}{2} \cdot \frac{n(n-1)}{2} - \frac{1}{2} \frac{n(n-1)^2}{4} = \frac{n(n^2-1)}{24}.$$
Equality holds if and only if $a_1 = \dots = a_n = \frac{n-1}{2}$. This can easily be arranged when $n$ is odd, by making student $i$ fall in love with students $i+1, \dots, i+\frac{n-1}{2}$ (counting cyclically).

When $n$ is even, this bound is clearly impossible to attain, and we must proceed differently. We investigate, for $n$ even, the minimal value of $a_1^2 + \dots + a_n^2$, subject to the condition $a_1 + \dots + a_n = \binom{n}{2}$.

Suppose first the sum of squares is at a minimum, but that $a_p - a_q \ge 2$ for some $p$ and $q$. We may then replace $a_p$ and $a_q$ by $a_p - 1$ and $a_q + 1$, respectively, which will serve to decrease the sum of squares:
$$(a_p - 1)^2 + (a_q + 1)^2 = a_p^2 + a_q^2 + 2(1 + a_q - a_p) < a_p^2 + a_q^2.$$
Consequently, when the sum of squares is at a minimum, the maximal difference among the numbers $a_i$ is at most $1$.

Suppose next, without loss of generality, that $a_1 = \dots = a_k = x$ and $a_{k+1} = \dots = a_n = x + 1$. Then
$$\binom{n}{2} = a_1 + \dots + a_n = kx + (n-k)(x+1) = nx + n - k \\ \Leftrightarrow k = nx + n - \binom{n}{2},$$
transforming the inequality $0 \le k \le n$ into
$$0 \le nx + n - \binom{n}{2} \le n \Leftrightarrow \frac{n-1}{2} - 1 \le x \le \frac{n-1}{2} \\ \Leftrightarrow x = \frac{n-2}{2}.$$
This corresponds to $k = \frac{n}{2}$, and so the minimum is attained when half of the $a_i$ equal $\frac{n-2}{2}$ and the remaining half equal $\frac{n}{2}$. The minimal quadratic sum is
$$\frac{n}{2} \left( \frac{n-2}{2} \right)^2 + \frac{n}{2} \left( \frac{n}{2} \right)^2 = \frac{n(n^2 - 2n + 2)}{4}.$$

We thus find
$$T \le \frac{n(n-1)(n-2)}{6} + \frac{1}{2} \cdot \frac{n(n-1)}{2} - \frac{1}{2} \cdot \frac{n(n^2 - 2n + 2)}{4} = \frac{n(n^2 - 4)}{24}$$