uniolympiads English

IMC 2023, Ημέρα 2, Θέμα 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}.
Πρωτότυπο από το επίσημο 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

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

(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}.

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 3–4. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;