Problem

Source: Polish MO Second round 2024 P3

Tags: combinatorics



Let $n \geq 2$ be a positive integer. There are $2n$ cities $M_1, M_2, \ldots, M_{2n}$ in the country of Mathlandia. Currently there roads only between $M_1$ and $M_2, M_3, \ldots, M_n$ and the king wants to build more roads so that it is possible to reach any city from every other city. The cost to build a road between $M_i$ and $M_j$ is $k_{i, j}>0$. Let $$K=\sum_{j=n+1}^{2n} k_{1,j}+\sum_{2 \leq i<j \leq 2n} k_{i, j}.$$Prove that the king can fulfill his plan at cost no more than $\frac{2K}{3n-1}$.