19th Turkish Mathematical Olympiad

The answer is $212$. Let $K_{2011,2011}$ be a complete bipartite graph in which all vertices of a set $A$ with $|A|=2011$ are connected to all vertices of $B$ with $|B|=2011$. We prove that there exists a monochromatic connected subgraph with $212$ vertices if edges of the graph $K_{2011,2011}$ are colored so that all edges incident to any given vertex are colored by at most $19$ colors. Indeed, let $i$th color. The set of colors used for coloring of all edges incident to $u$ will be denoted by $C(u)$. The Cauchy-Schwarz inequality implies that $$\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)\ge {\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,t$ with $f(s,t)\ge 212$ since $2\cdot \frac{2011}{19}=211.68$. Finally, we give an example with the greatest monochromatic connected component of size $212$ where only $19$ colors are used. Let us partition all vertices of $A$ and $B$ into sets $A_1,\dots ,A_{19}$ and $B_1,\dots ,B_{19}$ of sizes $105$ or $106$ and color all vertices between $A_i$ and $B_j$ into color $c(i,j)$ where $c(i,j)\equiv i+j(\mathrm{mod}19)$ and $1\le c(i,j)\le 19$. It can be readily seen that the maximal monochromatic connected component is of size $212$.