Question 91
There were $n$ boys $a_1, a_2, \dots, a_n$ and $n$ girls $b_1, b_2, \dots, b_n$ in a party. No boys shook hand with each other and no girls shook hand with each other and for each $i \in \{1, 2, \dots, n\}$, $a_i$ did not shake his hand with $b_i$. We want to divide all $2n$ people into groups satisfying the following two conditions.
1. In each group, the number of boys is equal to the number of girls.
2. In each group, no two people shook hands with each other.
Let $m$ be the number of pairs $(a_i, b_j)$ where $a_i$ shook his hand with $b_j$. Prove that it is possible to make the number of groups less than or equal to $2$ or $\frac{2m}{n} + 1$.
1. In each group, the number of boys is equal to the number of girls.
2. In each group, no two people shook hands with each other.
Let $m$ be the number of pairs $(a_i, b_j)$ where $a_i$ shook his hand with $b_j$. Prove that it is possible to make the number of groups less than or equal to $2$ or $\frac{2m}{n} + 1$.