남학생 $a_1,a_2,\ldots,a_n$과 여학생 $b_1,b_2,\ldots,b_n$이 있다. 남학생끼리는 악수를 하지 않았고, 여학생끼리도 악수를 하지 않았으며, 모든 $i\in\{1,2,\ldots,n\}$에 대하여, $a_i$와 $b_i$는 악수를 하지 않았다. 이 학생 전체를 다음 조건을 만족하는 소그룹들로 나누고자 한다.
(a) 소그룹 안의 남학생 수와 여학생 수가 같다.
(b) 소그룹 안에서는 서로 악수를 한 학생이 없다.
서로 악수를 한 남학생, 여학생의 쌍 $(a_i, b_j)$의 개수가 $m$일 때, 소그룹의 개수를 $2$ 또는 $\frac{2m}{n} +1$ 이하가 되도록 만들 수 있음을 증명하여라.
(2011년 3월 26일)