어떤 모임에서 학생 $A_1$, $A_2$, $\ldots$, $A_n$이 서로 악수를 하였다. 학생 $A_i$가 악수한 횟수를 $d_i$($1\le i\le n$)이라 할 때, $d_1+d_2+\cdots+d_n>0$이다. 다음 조건을 모두 만족하는 $i$, $j$ ($1\le i<j\le n$)이 존재함을 보여라.
(1) 학생 $A_i$와 학생 $A_j$는 악수를 하였다.
(2) $\displaystyle \frac{(d_1+d_2+\cdots+d_n)^2}{n^2} \le d_i d_j$
(두 학생이 악수를 여러 번 할 수도 있다.)
(2012년 8월 19일 오전, 2시간 30분)
$n$개의 집합 $A_1,A_2,\ldots,A_n$이 주어져있다. 집합 $\{1,2,\ldots,n\}$의 부분집합 $X$에 대해 \[N(X)=\{i\in \{1,2,\ldots,n\}-X : \text{모든 $j\in X$에 대해 }A_i\cap A_j\neq \emptyset\}\]이라 하자. 이때 $m$이 $3\le m\le n-2$인 정수이면, $\lvert{X}\rvert=m$이고 $\lvert{N(X)}\rvert\neq 1$인 $\{1,2,\ldots,n\}$의 부분집합 $X$가 반드시 존재함을 증명하여라.
(2012년 3월 24일 오후, 4시간 30분)
한 나라에 $n$개($n\ge 3$)의 도시와 두 개의 항공사가 있다. 임의의 두 도시 사이에는 이 두 도시를 오가는 항공편이 있고, 그 항공편은 모두 한 항공사가 운영한다. 한 여성 수학자가 한 도시에서 출발하여 그 도시로 돌아오는 여행을 하는데, 중간에 두 개 이상의 다른 도시를 각각 한번씩 거쳐서 돌아온다. 그 수학자가 어떤 도시에서 출발하든, 어떠한 경로를 택하든 상관없이 항상 두 항공사를 모두 이용하게 된다고 한다. 이러한 상황이 존재하도록 항공사를 배치할 수 있는 $n$ 중 가장 큰 값을 구하여라.
(2012년 8월 11일, 광저우, 둘째날 4시간동안 5~8번 문제)
$n>2$명의 선수가 참가한 어떤 테니스 대회에서는 임의의 두 선수는 서로 경기를 한번씩 한다고 하고 비기는 경기는 없다고 한다. 모든 경기가 끝난 후 선수들을 원형으로 잘 세웠더니, 임의의 세 선수 $A$, $B$, $C$에 대해 $A$, $B$가 원에서 이웃하면 $A$, $B$ 두 선수 중 적어도 한 명은 $C$를 이겼다고 한다. 이런 현상이 가능한 모든 $n$을 구하여라.
그래프에서 서로 이웃한 $t$개의 꼭지점을 $t$당이라 부르자. 어떤 꼭지점이 다른 모든 꼭지점과 이웃할 때 그 꼭지점을 중심점이라 부르자. 부등식 $\frac{3}{2}\le \frac{1}{2} n <k<n$을 만족하도록 두 정수 $n$, $k$가 주어져있다. 이때, $(k+1)$당이 없지만, 없던 변을 아무렇게나 추가해도 $(k+1)$당이 반드시 생기는 꼭지점 $n$개를 가진 그래프가 가질 수 있는 최소의 중심점 수는 몇 개인가?
소셜 네트웍 Mugbook이라는 곳에 무한히 많은 사람들이 등록하였다고 하자. 서로 다른 어떤 두 사람은 친구로 등록될 수 있는데, 각 사람은 유한명의 친구를 가질 수 있다고 한다. 모든 사람은 적어도 한 명의 친구는 있다고 하자. (친구 관계는 대칭적이라서 A가 B의 친구라면 B 역시 A의 친구이다.)
각 사람은 모두 친구 중 한 명을 뽑아 절친으로 지정한다. A가 B를 절친으로 등록한다고 하더라도 B는 A가 아닌 다른 사람을 절친으로 지정할 수도 있다. 누군가의 절친인 사람은 1-절친이라고 부르자. 일반적으로 어떤 정수 $n>1$에 대해, 어떤 사람이 $n$-절친이라는 말은, 그 사람이 $(n-1)$-절친인 사람의 절친이라는 것으로 정의하자. 모든 양의 정수 $k$에 대해 $k$-절친이 되는 사람을 인기인이라 부르자.
(a) 모든 인기인 각자는 어떤 인기인의 절친임을 증명하라.
(b) 만일 사람들이 무한히 많은 친구를 가질 수 있다면, 인기인이라고 하더라도 어떤 인기인의 절친이 아닐 수도 있음을 보여라.
(2012년 4월 13일, 둘쨋날, 4시간 반동안 4문제)