IMC 2023, Ημέρα 2, Θέμα 8
Let be a tree with vertices; that is, a connected simple graph on vertices that contains no cycle. For every pair of vertices, let denote the distance between and , that is, the number of edges in the shortest path in that connects with .
Consider the sums
Prove that
Πρωτότυπο από το επίσημο PDF

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.
Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.
Επίσημη λύση
(proposed by Slobodan Filipovski, University of Primorska, Koper)
Hint: There are pairs with ; in all other cases .
Solution. Let and let be the distances between the pairs of vertices in the tree . Thus
Since the tree has exactly edges, there are exactly pairs of vertices at distance one, that is, . Thus
From Cauchy inequality we have
The equality holds if and only if .
Now we minimize the expression , where .
It is clear that the minimal value is achieved for . Therefore we get
The equality holds for and , that is, the smallest value is achieved for the tree where pairs are at distance one, and the remaining pairs are at distance two. The unique tree which satisfies these conditions is the star graph . In this case it holds
Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 3–4. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.
Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.
Πώς πήγε;
Οι κινήσεις που σημειώνεις επιστρέφουν νωρίτερα στη διαλογή.