Posts Tagged ‘ 더블 카운팅 ’

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의 예고? ㅋㅋ

2010 KMO 여름학교 모의고사 2차 #2

더블 카운팅하니 한 문제 더. 얼마 전에 있었던 여름학교 모의고사의 2차 2번. 2차 1번과 마찬가지로 이번에 출제한 문제.

48명의 학생이 7개의 문제가 주어지는 경시대회에 참가한다. 시험이 끝난 후, 다음과 같은 사실이 알려졌다.
– 임의의 5문제에 대해 그들을 전부 푼 학생은 없었다.
– 임의의 3문제에 대해 그들을 전부 푼 학생은 정확히 5명이었다.
– 임의의 1문제에 대해 그를 푼 학생 수는 짝수였다.
이 때 한 문제만 푼 학생은 정확히 한 명임을 보여라.

문제에서 더블 카운팅을 써달라고 애원하는 것이나 마찬가지. 첫 조건에 의해 학생이 푼 문제 수는 4개 이하다. 4,3,2,1,0개의 문제를 푼 학생 수를 a,b,c,d,e라 하자. 그러면 d=1을 보이면 된다.
{(문제 A,B,C, 학생 X): X가 A,B,C를 풂}을 생각한다.
(1) 두 번째 조건에 의해, 원소의 개수는 5\binom{7}{3}=175.
(2) 한 편, 이 원소의 개수는 \binom{4}{3}a+\binom{3}{3}b=4a+b이다.
따라서 이 두 조건에 의해 4a+b=175가 된다. 여기서 음 아닌 정수 k에 대해 a=43-k,b=3+4k라 할 수 있다. 한 편, a+b+c+d+e=48이므로 48=a+b+c+d+e \geq a+b=46+3k가 되어 k=0이 된다. 곧 a=43,b=3,c+d+e=2가 된다.
한 편, 이번엔 {(문제 A, 학생 X): X가 A를 풂}을 보면 세 번째 조건에 의해 그 원소의 개수 4a+3b+2c+d는 짝수가 되어 bd는 기우성이 같다. 즉 d는 홀수가 되는데 d \leq c+d+e=2이므로, d=1이고 문제가 증명된다.

나중에 들은 이야기지만 이 문제가 2차 시험 중에서 가장 평균이 높았다고. 이제 더블 카운팅도 많이 정립된건가..

2010 Iran NMO #2, #6

2010 Iran NMO의 조합 문제 2번과 6번. 놀랍게도 둘 다 기초적인 더블 카운팅 문제였다. 이 중 2번은 올 봄에 있었던 통신강좌 (수행평가라고 이름이 바뀌었던데) 금주의 문제로 나오기도 했다.

2. 평면 위에 n개의 점이 있어 어떤 세 개도 일직선 위에 있진 않다고 한다. 이 때 이 점들 중 세 개를 택하여 만드는 삼각형 중 넓이가 1인 것의 개수는 \frac{2}{3}(n^2-n) 이하임을 보여라.

간단한 더블 카운팅. 집합 {(점 A, (점 B,C)): 삼각형 ABC의 넓이는 1}을 생각한다. 이 집합의 원소의 개수를 센다.
(1) 두 점 B,C를 미리 택하면 삼각형 ABC의 넓이가 1이 되게 하는 A의 자취는 BC에 평행한 직선 두 개이다. 따라서 어떤 세 점도 한 직선 위에 있지 않음에서 그러한 A는 최대 네 개이므로 원소의 개수는 최대 4\binom{n}{2}이다.
(2) 한 편 임의의 넓이가 1인 삼각형 하나에 대해, 그 삼각형이 이 집합에 나오는 가지수는 꼭지점 세 개 중에서 어느 것을 맨 앞에 쓰느냐의 문제이므로 세 번 나온다. 곧, 구하고자 하는 개수를 N이라 하면 원소의 개수는 3N이다.
따라서 이를 연립하면 3N \leq 4\binom{n}{2}이므로 N \leq \frac{2}{3}(n^2-n)이 성립한다.

6. n명의 학생이 있는 한 학교에 몇 가지 특별반이 있다. 각 학생은 자신이 원하는 어떤 특별반에도 개수에 제한 없이 들어갈 수 있다. 모든 특별반은 적어도 2명의 학생이 듣고 있다. 만약 두 개의 서로 다른 특별반이 두 명 이상의 공통 학생을 가지면, 두 특별반의 학생 수는 서로 다르다고 한다. 이 때 특별반의 개수는 (n-1)^2 이하임을 보여라.

약간 어렵지만 그래도 더블 카운팅. 학생 수가 k명인 특별반이 x_k개 있다고 하자. 이 특별반들에 대해 {(특별반, (학생 두 명 A, B)): 특별반에 학생 A,B가 속해 있음}의 원소의 개수를 센다.
(1) 각 특별반은 k명을 가지므로 그 중 두 명을 택하는 가지수는 \binom{k}{2}이다. 곧, 원소의 개수는 x_k\binom{k}{2}이다.
(2) 학생 두 명에 대해 그 둘을 동시에 포함하는 특별반들은 전부 학생 수가 달라야 한다. 곧, 학생 수가 k명이면서 이 둘을 포함하는 특별반은 최대 한 개이므로 원소 개수는 \binom{n}{2}이하이다.
따라서, x_k\binom{k}{2} \leq \binom{n}{2}, 곧 x_k \leq \frac{n(n-1)}{k(k-1)}이다. 따라서 특별반의 개수는 x_2+\cdots+x_n \leq n(n-1) \left( \frac{1}{1 \cdot 2} + \cdots + \frac{1}{(n-1)n} \right) = n(n-1)\left(1-\frac{1}{n} \right) = (n-1)^2이다.

나중에 조합론 2판 쓰게 된다면 추가할 문제.