24th Korean Mathematical Olympiad Final Round

Let $G$ be a graph on $2n$ vertices representing $n$ boys and $n$ girls such that two vertices are adjacent if they shook hands with each other.

(1) First let us show that it is true when $m<n$. Let $C_1,C_2,\dots ,C_k$ be components of $G$. Since $G$ has $2n$ vertices and less than $n$ edges, the number of components should be larger than $n$. Then ${\sum }_{i=1}^t|C_i|$ for $1\le t\le n+1$ are distinct positive integers less than or equal to $2n$. By the pigeonhole principle, there exist $a<b$ such that ${\sum }_{i=1}^a|C_i|\equiv {\sum }_{i=1}^b|C_i|(\mathrm{mod}n)$. Therefore $|C_{a+1}|+|C_{a+2}|+\cdots +|C_b|=n$. Let $A=C_{a+1}\cup C_{a+2}\cup \cdots \cup C_b$. Since $|A|=n$, the number of boys in $A$ is equal to the number of girls not in $A$. Thus we can make one group consisting of boys in $A$ and girls not in $A$ and another group consisting of boys not in $A$ and girls in $A$. Then we obtain 2 groups satisfying the conditions.

(2) Now let us assume that $m\ge n$. Because $a_i$ is not adjacent to $b_i$ for all $i$, there is at least one method to partition people into groups satisfying the conditions. Let $s$ be the minimum number of groups while satisfying the conditions. Let $V_1,V_2,\dots ,V_s$ be the groups partitioning all $2n$ people.

For all $1\le i<j<k\le s$, if we can merge 3 groups $V_i,V_j,V_k$ into two groups, then this contradicts to the assumption that $s$ is minimum. Thus, by (1), the number of edges among $V_i,V_j$, and $V_k$ is at least $\frac{|V_i\cup V_j|+|V_k|}{2}$. Let $S$ be the number of edges among $V_i,V_j$, and $V_k$ for all triples $i<j<k$. Then $$S\ge \frac{1}{2}\left(\genfrac{}{}{0ex}{}{s-1}{2}\right)\sum _{i=1}^s|V_i|=\frac{1}{2}\left(\genfrac{}{}{0ex}{}{s-1}{2}\right)(2n).$$

On the other hand, each edge is counted $s-2$ times in $S$. By the double counting, $S=(s-2)m$. We deduce that $m\ge \frac{s-1}{2}n$. We conclude that $s\le \frac{2m}{n}+1$. $\square$