MathDB

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

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}

3