2011 FKMO #3

2019년 6월 19일 에 작성됨 FKMO(2011)

0 2018년 5월 14일

남학생 $a_1 ,a_2 ,\cdots ,a_n$과 여학생 $b_1 ,b_2 ,\cdots ,b_n$이 있다. 남학생끼리는 악수를 하지 않았고, 여학생끼리도 악수를 하지 않았으며, 모든 $i \in \{ 1,2,\cdots ,n \} $에 대하여, $a_i$와 $b_i$는 악수를 하지 않았다. 이 학생 전체를 다음 조건을 만족하는 소그룹들로 나누고자 한다.

조건 1: 소그룹 안의 남학생 수와 여학생 수는 같다.

조건 2: 소그룹 안에서는 서로 악수를 한 학생이 없다.

서로 악수를 한 남학생, 여학생의 쌍 $(a_i ,b_j )$의 개수가 $m$일 때, 소그룹의 개수를 $2$ 또는 $\frac{2m}{n}+1$ 이하가 되도록 만들 수 있음을 증명하여라.

 
    \
  • Liked by
Reply
Loading more replies