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}$.
Problem
Source: Polish MO Second round 2024 P3
Tags: combinatorics
Tintarn
11.02.2024 01:32
First, note that the expression for $K$ is a bit misleading as it includes costs for the roads $k_{i,j}$ with $2 \le i<j \le n$ that we are of course not going to build. So we should instead work with $K'=\sum_{i=1}^n \sum_{j=n+1}^{2n} k_{i,j}+\sum_{n+1 \le i<j \le 2n} k_{i,j} \le K$ which is exactly the sum of the weights of the $\frac{n(3n-1)}{2}$ that we could potentially want to build.
Note that w.l.o.g. we build exactly $n$ of them, so the expression $\frac{2K'}{3n-1} \le \frac{2K}{3n-1}$ (which we will obtain as an upper bound) nicely expresses that we can choose $n$ streets with "not-more-than-average" costs (and this is clearly optimal if all the streets are equally expensive).
But of course we can not just build the $n$ cheapest streets, so we need to be a bit more clever.
Indeed, the claim will follow immediately if we can partition the $\frac{n(3n-1)}{2}$ into groups of at least $n$ streets each, such that if we build any $n$ streets from any one of the groups, we will obtain a connection between all cities.
Indeed, in that case, there will be a group which has "not-more-than-average" costs on average, and then we can just build the $n$ cheapest streets from this group.
So from now on we can completely ignore the costs and we are left with a completely graph-theoretical question of partitioning the streets as above.
The key for the construction will be the following well-known fact (sometimes known as the Walecki decomposition): If $m$ is odd, then the complete graph $K_m$ can be partitioned into $\frac{m-1}{2}$ Hamiltonian circles. By deleting one vertex, we see that if $m$ is even, then $K_m$ can be partitioned into $\frac{m}{2}$ Hamiltonian paths.
Now first suppose that $n$ is even. Apply the fact above to the graph on the $n+1$ vertices $1,n+1,\dots,2n$. We then choose the groups to be the $n+1$ edges from each such Hamiltonian circle and the remaining groups are just $\{((i,n+1),\dots,(i,2n)\}$ with $2 \le i \le n$. This clearly works.
For $n$ odd, we again consider the $n+1$ vertices $1,n+1,\dots,2n$ and use the partition into Hamiltonian paths of length $n$ for our groups. Again, we can just choose $\{(i,n+1),\dots,(i,2n)\}$ with $2 \le i \le n$ as the remaining groups.