A graph theoretic problem Suppose that we have a set of $n^2$ points in the plane ( $n$ is even ) . They are joined using  directed edges of $n-1$ colours  according to the following scheme :----
$\bullet$ Between any two points , say $A$ and $B$ , directed edges of exactly one colour (say , red ) point from $A \rightarrow B$ and $B \rightarrow A$ .
    [There may be other edges between $A$ and $B$ ; but there is no colour apart from red , such that there are edges of that colour directed both from  $A \rightarrow B$ and $B \rightarrow A$]
$\bullet$ Call a triplet of points $(X,Y,Z)$ well-behaved if there is an edge of same colour directed from $X \rightarrow Y$ and $Y \rightarrow Z$ where $X,Y,Z$ are pairwise distinct.
Determine the smallest possible $k$ such that , no-matter how we join the $n^2$ points according to the above-mentioned scheme , we get at least $k$ well-behaved triples . 
 A: Apparently, if we remove an edge $X\to Y$ for which there is no edge $Y\to X$ of the same colour, we do not break the condition and at most decrease the number of well-behaved triples.
Hence we may assume wlog. that our graph has only edges for which an inverse edge of the same colour exists. This allows us to consider the edges as undirected. In effect, we have an edge-coloured simple undirected graph. By the requirement, the graph is complete.
So every vertex $Y$ has exactly $n^2-1=(n+1)(n-1)$ neighbours. If colour $i$ occurs $n_i$ times among the $(n+1)(n-1)$ edges at $Y$, then $Y$ is the midpoint of $\sum_{i=1}^{n-1}{n_i\choose 2}$ well-behaved triples.
This sum is minimal if all summands are equal, and in that case it takes the value $(n-1)\cdot {n+1\choose 2})=\frac{n^3-n}{2}$.
Summing over all $n^2$ possible choices of $Y$, we see that there are at least
$$\tag1 \frac{n^5-n^3}{2}$$
well-behaved triples.
So far, $(1)$ is only a lower bound. The construction I had thought of to actually achieve that bound turned out not to work while I composed this answer. Note that we did not make use of the fact that $n$ is even.
