Olympiad Maths Prep

Library / /4 of 5

Combinatorics Difficulty 6.9 National olympiad Prove it Turkey

Between any two cities of country AA consisting of 20112011 cities and country BB consisting of 20112011 cities there is a unique direct two way flight organized by some airway company. For each given city there are at most 1919 different airway companies operating flights related to this city. Determine the maximum possible value of the integer kk such that no matter how these flights are arranged there are kk cities connected (not necessarily directly) only by the flights of some fixed airway company.

Solution

**The answer is 212212.**
Let K2011,2011K_{2011,2011} be a complete bipartite graph in which all vertices of a set AA with A=2011|A| = 2011 are connected to all vertices of BB with B=2011|B| = 2011. We prove that there exists a monochromatic connected subgraph with 212212 vertices if edges of the graph K2011,2011K_{2011,2011} are colored so that all edges incident to any given vertex are colored by at most 1919 colors. Indeed, let ii-th color degree of a vertex vv be di(v)d_i(v). For each connected pair of vertices (u,v)(u, v), let us define f(u,v)=di(u)+di(v)f(u, v) = d_i(u) + d_i(v) where the edge connecting uu and vv is colored by the ii-th color. The set of colors used for coloring of all edges incident to uu will be denoted by C(u)C(u). The Cauchy-Schwarz inequality implies that
12uA,vBf(u,v)=uA,iC(u)di2(u)(uA,iC(u)di(u))21201119=20112201119 \frac{1}{2} \sum_{u \in A, v \in B} f(u, v) = \sum_{u \in A, i \in C(u)} d_i^2(u) \geq \left( \sum_{u \in A, i \in C(u)} d_i(u) \right)^2 \cdot \frac{1}{2011 \cdot 19} = 2011^2 \cdot \frac{2011}{19}
Therefore, by the pigeon hole principle there exist vertices s,ts, t with f(s,t)212f(s, t) \ge 212 since 2201119=211.682 \cdot \frac{2011}{19} = 211.68.
Finally, we give an example with the greatest monochromatic connected component of size 212212 where only 1919 colors are used. Let us partition all vertices of AA and BB into sets A1,,A19A_1, \dots, A_{19} and B1,,B19B_1, \dots, B_{19} of sizes 105105 or 106106 and color all vertices between AiA_i and BjB_j into color c(i,j)c(i, j) where c(i,j)i+j(mod19)c(i, j) \equiv i + j \pmod{19} and 1c(i,j)191 \le c(i, j) \le 19. It can be readily seen that the maximal monochromatic connected component is of size 212212.

Looking for a route rather than an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.