Let $n$ be an integer greater than $1$, and let $p$ be a prime divisor of $n$. A confederation consists of $p$ states, each of which has exactly $n$ airports. There are $p$ air companies operating interstate flights only such that every two airports in different states are joined by a direct (two-way) flight operated by one of these companies. Determine the maximal integer $N$ satisfying the following condition: In every such confederation it is possible to choose one of the $p$ air companies and $N$ of the $np$ airports such that one may travel (not necessarily directly) from any one of the $N$ chosen airports to any other such only by flights operated by the chosen air company.
Problem
Source: Romania TST 2015 Day 5 Problem 2
Tags: graph theory, combinatorics, Romanian TST
05.06.2015 16:09
Switch to graph theoretical notation : a p-partite complete graph $K_{n,n,...,n}$ has its edges coloured in $p$ distinct colours,determine the minimal size of the largest connected component in the colour subgraphs $G_i$,$i=1,2,...p$. I claim the required size is $n$,now the problem naturally splits into 2 parts: 1)Any colouring of the big graph generates a unicoloured connected component on $n$ vertices.Assume there is one that does not;consider now the colour which is used the most,assume it is colour 1.The big graph has exactly $\frac{n^2p(p-1)}{2}$ edges.Then $G_1$ has at least $\frac{n^2(p-1)}{2}$ edges. Now split $G_1$ into connected components;say there are $k$ of them.Then none of them has more than $n-1$ vertices,from which $k>p$.Let's say these components have size $x_i \le n-1,i=1,2,...,k$ with $\sum x_i=np$.Since the big graph was p-partite,so is $G_1$.Apply then Turan's (no p+1 cliques) on each of the $k$ connected components to get that the total number of edges in the connected components,and consequently the total number of edges in $G_1$,does not exceed $\frac{p-1}{2p}\sum x_i^2$.We now have lower and upper bounds for the number of edges in $G_1$,uniting them we get that $\frac{p-1}{2p}\sum x_i^2 \ge \frac{n^2(p-1)}{2}$,equiv. to $sum x_i^2\ge pn^2$.But Karamata applied to the strictly convex function $x^2$ and k-uplets $(n,n,...,n,0,0,...,0)$ and $(x_1,x_2,...,x_k)$ implies exactly the opposite inequalty,contradiction. 2)There exists a graph for which the largest connected component is of size exactly $n$.For this,we group all $n$ vertices on a shore in $p$ equisized groups.Now take group $i$ from shore $k$ and group $j$ from shore $l$.We colour the edges between the 2 groups in the colour which is equal to $1+(j-i)(l-k)^-1$ in $Z_p$.It is readily checkable that each color graph $G_i$ contains exactly $p$ size-$n$ connected components of the form $K_{d,d,...,d}$,where $d=\frac{n}{p}$,so the example is correct,and we are done.