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판 쓰게 된다면 추가할 문제.

Advertisements
  1. August 24th, 2010

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: