Mongolian Mathematical Olympiad

We are going to give a construction of coloring, whose number of angles with different colored sides is greater than $\binom{k}{2} \cdot \left[\frac{n}{k}\right]^2 \cdot n$.

Case I. Let $k$ be an odd number. Let $A_1, \dots, A_k$ be subsets of $\{A_0, A_1, \dots, A_n\}$ such that $A_1 \cup \dots \cup A_k = \{A_0, A_1, \dots, A_n\}$, $A_i \cap A_j = \emptyset$ for $i \neq j$, and $\left[\frac{n}{k}\right] \le |A_i| \le \left[\frac{n}{k}\right] + 1$.
Let us color the edges between $A_0$ and $A_i$ with color $i$, and color the edges between $A_i$ and $A_j$ with color $\frac{k+1}{2}(i+j) \pmod{k}$.

Case II. Let $k$ be an even number.

Lemma. If $k$ is even, we can color a complete graph on $k$ points with $k-1$ colors, so that edges with a general vertex have different colors.
If we color the edges between $A_i$ and $A_j$ with the color given by the lemma, we'll have the construction we desired.