Question 159
Country "U" has cities $A_1, A_2, \dots, A_n$. They are connected with flights so that one can get from any city to any other city with layovers. Let $d_{i,j}$ be the smallest amount of flights needed to get from city $A_i$ to city $A_j$, and let $d$ be the total number of flights in country "U" and let
$$
D = d_{1,1} + d_{1,2} + \dots + d_{1,n} + d_{2,3} + d_{2,4} + \dots + d_{2,n} + \dots + d_{n-1,n}.
$$
Show that:
$$
d + \frac{D}{n-1} \le \frac{1}{2}(n+1)(n+2).
$$
$$
D = d_{1,1} + d_{1,2} + \dots + d_{1,n} + d_{2,3} + d_{2,4} + \dots + d_{2,n} + \dots + d_{n-1,n}.
$$
Show that:
$$
d + \frac{D}{n-1} \le \frac{1}{2}(n+1)(n+2).
$$