MathDB
The king builds a connected graph optimally

Source: Polish MO Second round 2024 P3

February 9, 2024
combinatorics

Problem Statement

Let n≥2n \geq 2 be a positive integer. There are 2n2n cities M1,M2,…,M2nM_1, M_2, \ldots, M_{2n} in the country of Mathlandia. Currently there roads only between M1M_1 and M2,M3,…,MnM_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 MiM_i and MjM_j is ki,j>0k_{i, j}>0. Let K=∑j=n+12nk1,j+∑2≤i<j≤2nki,j.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 2K3n−1\frac{2K}{3n-1}.
Back to ProblemsView on AoPS