uniolympiads Ελληνικά

IMC 2023, Day 2, Problem 8

Let TT be a tree with nn vertices; that is, a connected simple graph on nn vertices that contains no cycle. For every pair u,vu, v of vertices, let d(u,v)d(u, v) denote the distance between uu and vv, that is, the number of edges in the shortest path in TT that connects uu with vv.

Consider the sums

W(T)=∑{u,v}⊆V(T)u≠vd(u,v)andH(T)=∑{u,v}⊆V(T)u≠v1d(u,v).W(T) = \sum_{\substack{\{u,v\} \subseteq V(T) \\ u \ne v}} d(u, v) \quad \text{and} \quad H(T) = \sum_{\substack{\{u,v\} \subseteq V(T) \\ u \ne v}} \frac{1}{d(u, v)}.

Prove that

W(T)⋅H(T)≥(n−1)3(n+2)4.W(T) \cdot H(T) \ge \frac{(n-1)^3(n+2)}{4}.
Original from the official PDFLet T be a tree with n vertices; that is, a connected simple graph on n vertices that contains no cycle. For every pair u, v of vertices, let d(u, v) denote the distance between u and v, that is, the number of edges in the shortest path in T that connects u with v. Consider the sums X X 1 . W (T ) = d(u, v) and H(T ) = d(u, v) {u,v}⊆V (T ) u̸ = v Prove that W (T ) · H(T ) ≥ {u,v}⊆V (T ) u̸ = v (n − 1) 3 (n + 2) . 4

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

(proposed by Slobodan Filipovski, University of Primorska, Koper)

Hint: There are n−1n-1 pairs u,vu,v with d(u,v)=1d(u,v) = 1; in all other cases d(u,v)≥2d(u,v) \ge 2.

Solution. Let k=(n2)k = \binom{n}{2} and let x1≤x2≤…≤xkx_1 \le x_2 \le \ldots \le x_k be the distances between the pairs of vertices in the tree TT. Thus

W(T)⋅H(T)=(x1+x2+…+xk)⋅(1x1+1x2+…+1xk).W(T)\cdot H(T) = (x_1 + x_2 + \ldots + x_k)\cdot\left(\frac{1}{x_1} + \frac{1}{x_2} + \ldots + \frac{1}{x_k}\right).

Since the tree has exactly n−1n-1 edges, there are exactly n−1n-1 pairs of vertices at distance one, that is, x1=x2=…=xn−1=1x_1 = x_2 = \ldots = x_{n-1} = 1. Thus

W(T)⋅H(T)=(n−1+xn+xn+1+…+xk)⋅(n−1+1xn+1xn+1+…+1xk)==(n−1)2+(n−1)((xn+1xn)+…+(xk+1xk))++(xn+…+xk)(1xn+…+1xk).\begin{aligned} W(T)\cdot H(T) &= (n - 1 + x_n + x_{n+1} + \ldots + x_k)\cdot\left(n - 1 + \frac{1}{x_n} + \frac{1}{x_{n+1}} + \ldots + \frac{1}{x_k}\right) = \\ &= (n-1)^2 + (n-1)\left(\left(x_n + \frac{1}{x_n}\right) + \ldots + \left(x_k + \frac{1}{x_k}\right)\right) + \\ &\quad + (x_n + \ldots + x_k)\left(\frac{1}{x_n} + \ldots + \frac{1}{x_k}\right). \end{aligned}

From Cauchy inequality we have

(xn+…+xk)(1xn+…+1xk)≥(1+1+…+1)2=(k−n+1)2=(n−1)2(n−2)24.(x_n + \ldots + x_k)\left(\frac{1}{x_n} + \ldots + \frac{1}{x_k}\right) \ge (1 + 1 + \ldots + 1)^2 = (k - n + 1)^2 = \frac{(n-1)^2(n-2)^2}{4}.

The equality holds if and only if xn=xn+1=…=xkx_n = x_{n+1} = \ldots = x_k.

Now we minimize the expression (xn+1xn)+…+(xk+1xk)\left(x_n + \frac{1}{x_n}\right) + \ldots + \left(x_k + \frac{1}{x_k}\right), where xi∈[2,n−1]x_i \in [2, n-1].

It is clear that the minimal value is achieved for xn=xn+1=…=xk=2x_n = x_{n+1} = \ldots = x_k = 2. Therefore we get

W(T)⋅H(T)≥(n−1)2+(n−1)((2+12)(k−n+1))+(n−1)2(n−2)24=(n−1)3(n+2)4.W(T)\cdot H(T) \ge (n-1)^2 + (n-1)\left(\left(2 + \frac{1}{2}\right)(k - n + 1)\right) + \frac{(n-1)^2(n-2)^2}{4} = \frac{(n-1)^3(n+2)}{4}.

The equality holds for x1=…=xn−1=1x_1 = \ldots = x_{n-1} = 1 and xn=xn+1=…=xk=2x_n = x_{n+1} = \ldots = x_k = 2, that is, the smallest value is achieved for the tree where n−1n-1 pairs are at distance one, and the remaining k−(n−1)=(n−1)(n−2)2k - (n-1) = \frac{(n-1)(n-2)}{2} pairs are at distance two. The unique tree which satisfies these conditions is the star graph SnS_n. In this case it holds

W(Sn)⋅H(Sn)=(n−1)2⋅(n−1)(n+2)4=(n−1)3(n+2)4.W(S_n)\cdot H(S_n) = (n-1)^2\cdot\frac{(n-1)(n+2)}{4} = \frac{(n-1)^3(n+2)}{4}.

Transcribed from the official solutions, pages 3–4. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?