Country Connected By One Way Roads

Let's solve this problem for all odd $n \in \mathbb{N}$ instead of $2015$ . Let the cities be $C_1, C_2, \cdots , C_n$ , and for all $1 \leq i \leq n,$ let $D_i$ be the number of cities directly approachable from city $C_i$ .

Since the sum of good and non-good triples is always equal to $\dbinom{n}{3}$ , instead of trying to maximize the number of good triples of towns, we try to minimize the number of non-good triples of towns.

Note that in any non-good triple of towns, there must exist one town from which the other two towns can be directly reached. Call that town the pivot of that non-good triple. For example, if cities $C_2, C_3$ can be reached from $C_1$ , $\{C_1, C_2, C_3\}$ forms a non-good triple with pivot $C_1$ .

Note that the number of non-good triples with pivot $C_i$ is equal to $\dbinom{D_i}{2}$ . Hence, the total number of non-good triples is equal to $\displaystyle \sum_{i=1}^{n} \dbinom{D_i}{2}$ , and hence, the total number of good triples is equal to $\dbinom{n}{3} - \displaystyle \sum_{i=1}^{n} \dbinom{D_i}{2}$ .

Now, note that $\displaystyle \sum_{I=1}^{n} D_i = \dbinom{n}{2} = \dfrac{n(n-1)}{2}$ since both sides are equal to the total number of roads. By Cauchy Schwartz, $\begin{aligned} \dbinom{n}{3} - \displaystyle \sum_{i=1}^{n} \dbinom{D_i}{2} & = \dbinom{n}{3} - \dfrac{1}{2} (D_i^2-D_i) \\ & \geq \dbinom{n}{3} - \dfrac{1}{2n^2} \left( \displaystyle \sum_{i=1}^{n} D_i \right) ^2 - \dfrac{1}{2} \displaystyle \sum_{i=1}^{n} D_i \\ & = \dfrac{n(n-1)(n+1)}{24}. \end{aligned}$ Equality holds when exactly $\dfrac{n-1}{2}$ roads originate from each city.

We shall prove by a trivial induction that this is possible for all odd $n$ .

For the base case $n=3$ , just consider three cities which form a good triple.

Suppose such a construction exists for $2k+1$ , so that each city has exactly $k$ roads originating from it. Add two other cities, $C_{2k+2}$ and $C_{2k+3}$ so that cities $C_1, C_2, \cdots , C_k$ and $C_{2k+3}$ can be directly reached from $C_{2k+2}$ and cities $C_{k+1}, C_{k+2}, \cdots, C_{2k+1}$ can be directly reached from $C_{2k+3}$ - note that each city can now be reached from exactly $k+1$ other cities, so we're done.

Hence, our answer is $\dfrac{n(n-1)(n+1)}{24}$ . For this particular case, our answer is $\boxed{360}$ .

---

This problem is taken from a problem in a MOP red group homework problem.

Side problem : Suppose that each city is approachable from at least one other city. Prove that there must exist a good triple of cities.