2010 KMO #7

7. 정보기관에서 테러리스트 용의자 2000명 사이에 휴대전화 통화가 있었는지 여부를 조사하였다. 그런데 서로 겹치지 않는 3명씩의 두 모임 A,B를 뽑아보면 AB 사이에는 반드시 통화하지 않았던 쌍이 있었다. 이 때, 통화한 적이 있는 쌍의 개수는 201000보다 작음을 보여라.

더블 카운팅!

그래프로 바꾼 후 각각의 차수를 d_i라 하고 전체 변의 개수 (=통화한 적이 있는 쌍의 개수)를 e=\frac{1}{2} \sum d_i라 한다. 집합 {(A,(B_1,B_2,B_3)): i=1,2,3에 대해 AB_i는 아는 사이}을 생각한다.
(1) 임의의 A에 대해 그가 아는 세 사람을 택하면 되므로 전부 \sum \binom{d_i}{3}가지.
(2) 그런데 B_1,B_2,B_3을 미리 택하고 나면 그들과 전부 통화한 사람은 최대 두 명이다. 세 명이면 조건에 모순. 따라서 저 집합의 원소의 개수는 최대 2 \binom{2000}{3}.
따라서 \displaystyle 2 \binom{2000}{3} \geq \sum \binom{d_i}{3} \geq 2000 \binom{\frac{2e}{2000}}{3}가 젠센 부등식으로 성립. 이를 정리하면 2 \cdot 1999 \cdot 1998 \geq x(x-1)(x-2)가 성립한다. (x=\frac{1000}{e}) 우변을 f(x)라 하면 f는 증가함수이고 f(201)=200^3-200 > (LHS)이므로 f(x) \leq 2 \cdot 1999 \cdot 1998 < f(201), 즉 e < 201000를 의미한다.

더블 카운팅 중에서도 Iran NMO #2와 비슷하다. 통강은 KMO의 예고? ㅋㅋ

Advertisements
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: