소셜 네트웍 Mugbook이라는 곳에 무한히 많은 사람들이 등록하였다고 하자. 서로 다른 어떤 두 사람은 친구로 등록될 수 있는데, 각 사람은 유한명의 친구를 가질 수 있다고 한다. 모든 사람은 적어도 한 명의 친구는 있다고 하자. (친구 관계는 대칭적이라서 A가 B의 친구라면 B 역시 A의 친구이다.)

각 사람은 모두 친구 중 한 명을 뽑아 절친으로 지정한다. A가 B를 절친으로 등록한다고 하더라도 B는 A가 아닌 다른 사람을 절친으로 지정할 수도 있다. 누군가의 절친인 사람은 1-절친이라고 부르자. 일반적으로 어떤 정수 $n>1$에 대해, 어떤 사람이 $n$-절친이라는 말은, 그 사람이 $(n-1)$-절친인 사람의 절친이라는 것으로 정의하자. 모든 양의 정수 $k$에 대해 $k$-절친이 되는 사람을 인기인이라 부르자.

(a) 모든 인기인 각자는 어떤 인기인의 절친임을 증명하라.

(b) 만일 사람들이 무한히 많은 친구를 가질 수 있다면, 인기인이라고 하더라도 어떤 인기인의 절친이 아닐 수도 있음을 보여라.

(2012년 4월 13일, 둘쨋날, 4시간 반동안 4문제)