58th Ukrainian National Mathematical Olympiad

Show that: $$d+\frac{D}{n-1}\le \frac{1}{2}(n+1)(n+2).$$

Let $i\ne j$, and let the shortest path between $A_i$ and $A_j$ be the following: $A_i=A_{{\gamma }_0},A_{{\gamma }_1},\dots ,A_{{\gamma }_k}=A_j$. Let $X$ be the set of such vertices ($k+1$ vertices), and let $Y$ be the set of all other vertices ($n-k-1$ vertices total). The number of edges that connects vertices inside $Y$ is not greater than $C_{n-k-1}^2$. All edges that connect vertices inside $X$ are the edges of the shortest path, otherwise there exists shorter path between $A_i$ and $A_j$. Therefore, there are exactly $k$ edges.

If $A\in Y$, then there are 3 or less edges that connect $A$ with vertices from $X$. Otherwise, there exists shorter path than the one that has $k$ edges. Therefore, there exists not more than $3(n-k-1)$ edges that connect vertices from $X$ and vertices from $Y$. Thus, $$\begin{array}{rl}d\le C_{n-k-1}^2+k+3(n-k-1)& =\frac{1}{2}(n^2+3n-4+k^2-k-2kn)\le \\ & (k<n,\text{ hence }kn<n^2)\\ \le \frac{1}{2}(n^2+3n-4)-\frac{n+1}{2}k& \Rightarrow d+\frac{n+1}{2}{d}_{i,j}\le \frac{1}{2}(n^2+3n-4),\text{ thus}\\ \sum _{1\le i<j\le n}\left(d+\frac{n+1}{2}{d}_{i,j}\right)& \le \frac{1}{2}{C}_n^2(n^2+3n-4),\text{ so}\\ C_n^{2}d+\frac{n+1}{2}D& \le \frac{1}{2}{C}_n^2(n^2+3n-4).\end{array}$$

The given inequality can be obtained by dividing inequality by $C_n^2$ and using $$\frac{n+1}{n(n-1)}\ge \frac{1}{n-1}\text{and}{n}^2+3n-4\le n^2+3n+2.$$