China Hong Kong Mathematical Olympiad

$n$ can be any odd integer larger than $1$.

We use terminologies in graph theory. We need to colour all edges of the complete graph of $n$ vertices in $n$ colours $C_1, C_2, \dots, C_n$ such that for any three distinct colours, there exists a triangle whose edges are of these three colours.

Note that there are $\binom{n}{3}$ triangles as well as $\binom{n}{3}$ triples of colours. Therefore, the triangles and the triples of colours are in one-to-one correspondence.

For each colour $C_j$, there are $\binom{n-1}{2}$ triples of colours consisting of $C_j$ since we need to choose two more colours from the remaining $n-1$ colours. On the other hand, for every edge of colour $C_j$, there are $n-2$ triangles containing this edge since we need to choose one more vertex from the remaining $n-2$ vertices. Therefore, there are exactly
$$\frac{1}{n-2} \binom{n-1}{2} = \frac{n-1}{2}$$
edges of colour $C_j$. This implies $n$ must be odd.

We now provide a colouring for odd $n$. For any vertices $V_i$ and $V_j$, we use colour $C_r$ to colour the edge joining them where $r \equiv i + j \pmod{n}$. It suffices to show that for any distinct triples $r_1, r_2, r_3$, the system
$$\begin{cases} i + j \equiv r_1 \pmod{n}, \\ j + k \equiv r_2 \pmod{n}, \\ k + i \equiv r_3 \pmod{n} \end{cases}$$
has a unique solution in $i, j, k \pmod{n}$ such that $i, j, k$ are pairwise incongruent modulo $n$. Indeed, we readily find that
$$i \equiv 2^{-1}((i + j) - (j + k) + (k + i)) \equiv 2^{-1}(r_1 - r_2 + r_3) \pmod{n},$$
and similarly $j \equiv 2^{-1}(r_1 + r_2 - r_3) \pmod{n}$ and $k \equiv 2^{-1}(-r_1 + r_2 + r_3) \pmod{n}$. These are incongruent because $r_1, r_2, r_3$ are incongruent modulo $n$. This completes the proof.