Posts Tagged ‘ 조합 ’

2010 JMO #3

3. 2010개의 섬이 있고, 그 섬들을 연결하는 2009개의 다리가 있다. 어떤 두 개의 섬에 대해서도 1개의 다리가 둘을 연결하거나 다리가 없거나 둘 중의 하나라 하고, 다리의 양 끝은 서로 다른 두 개의 섬이라 하자. 또한, 임의의 두 섬을 골라도 한 섬에서 다른 섬으로 다리를 몇 번 건넘으로써 갈 수 있다고 한다.
이제, 모든 섬이 한 통의 편지를 임의의 섬에 보낸다고 한다. (단, 자기 자신에게 편지를 보내는 것도 가능하다.) 이 때, 다음 사실이 판명되었다.
“섬 A와 섬 B가 다리로 연결되어 있으면, 섬 A의 편지의 목적지와 섬 B의 편지의 목적지는 서로 다리로 연결된 두 섬이거나, 같은 섬이다.
이 때, 다음 (1)과 (2) 중 적어도 하나가 성립함을 보여라.
(1) 자기 자신에게 편지를 보낸 섬이 존재한다.
(2) 서로 편지를 교환하고, 다리로 연결되어 있는 두 섬이 존재한다.

그래프로 바꾸면 단순그래프인데 2010개의 점, 2009개의 변을 갖고 있고 연결그래프가 되어야 한다. 곧 이 그래프는 수형도로 회로가 없다. 편의상 도시 X가 편지를 보낸 도시를 f(X)라 하자. 그러면 보여야할 것은 f(X)=XX가 존재함을 보이거나 f(X)=Y,f(Y)=XX,Y가 존재함을 보이면 된다. 귀류법으로 그런 경우가 없음을 가정하자. 그리고 수형도이기 때문에 X에서 f(X)로 가는 경로는 유일하게 존재하는데 그 길이를 d(X)라고 하자.

먼저 임의의 도시 X_0을 택한다. 그리고 d(X_0) \geq 2임을 가정하자. 그러면 X_0에서 f(X_0)으로 가는 경로가 있는데 그 경로에서 X_0 바로 다음 점을 X_1이라 한다. 마찬가지로 X_1에서 f(X_1)으로 가는 경로에서 X_1의 다음 점을 X_2라 하고, 계속 정의한다. 그러면 0 \leq d(X_{i+1})-d(X_i) \leq 2임을 보일 수 있다. 그런데 d(X_{i+1})=d(X_i)인 경우는 X_i에서 f(X_i)까지 이어진 경로 위에 f(X_{i+1})이 없음을 의미한다. 즉 새로운 점이 하나 필요하게 된다. 따라서 d(X_{i+1})=d(X_i)인 경우는 무수히 많이 나올 수 없어서 d(X_i)는 계속 감소해야만 한다. 그러면서도 0이 되어선 안 된다. (d(X_i)=0이면 X_i=f(X_i), 모순) 그러면 언젠가 d(X_n)=1n이 존재하게 된다. (만약 d(X_0)=1이었다면 바로 n=0인 경우로 보면 된다.)

이제 m \geq n인 경우 X_{m+1}=f(X_m)이 되어야 한다. 이 때 앞에서와 비슷한 논의로 계속 새로운 점이 나올 수 없어서 언젠가 f(X_m)=X_m이거나 f(X_m)=X_{m-1}이 되어야 한다. 이는 모순. 끝

풀기 전에 좀 브레인스토밍하다보면 문제가 어떤 의미인지 또 어떤 풀이인지 감은 잡히는데 그걸 표현하는게 다소 짜증나는 문제

Advertisements

2010 KMO 여름학교 “조합등식” 강의록

저번 8월의 여름학교에 조합론 강의를 했다. 많은 토픽 중에서 조합 등식에 대해 강의를 하였는데 그 때 나누어주었던 강의록을 올린다. 사실 중등부의 프린트는 아주 약간 다른 버젼이긴 한데, 차이래봤자 중등부엔 이항계수에 대한 개념적 설명이 더 추가됐고 맨 마지막 J 챕터를 없앤 것에 불과하니 고등부 버젼을 올린다. 조합등식이 올림피아드에 반드시 나오리란 보장도 없지만 증명하면서 많은 테크닉을 익힐 수 있어 더 없이 좋은 연습문제가 되리라 생각. 게다가 2010 USA TST #8로 조합등식 문제가 하나 나오기도 했지..

챕터 미리보기!

A. 조합등식이란
B. 생성함수
C. 생성함수의 이용 리뷰
D. 기초 조합등식
E. 포함과 배제의 원리
F. 차분법
G. 부호가 붙은 조합등식
H. 응용 조합등식
I. 심화 조합등식
J. 도전 조합등식

파일: 조합등식 강의록

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 #4

4. 총 n명(n \geq 4)의 외교관들이 모여 있다. 임의의 네 외교관 A,B,C,D에 대하여, AB가 악수를 했고 BC가 악수를 했으며 CD가 악수를 했다면, 세 쌍 AC, AD, BD 중 악수를 했던 쌍이 반드시 존재한다. 이 때 다음을 증명하여라.
(a) 전체 외교관을 다음 성질이 만족하도록 공집합이 아닌 두 집합 X,Y로 나눌 수 있다. X에 속한 모든 외교관이 Y에 속한 어떤 외교관과도 악수를 하지 않았거나, X에 속한 모든 외교관이 Y에 속한 모든 외교관과 악수를 하였다.
(b) 어떤 두 외교관 A,B가 있어서 A,B 이외의 외교관 중에 A와 악수한 사람들의 모임과 B와 악수한 사람들의 모임이 같다.

약간 까다롭지만 어떻게 되긴 되네..

먼저 편의상 두 무리가 서로 악수를 안 했으면 적대관계, 전부 악수를 했으면 우호관계라 하자.

(a) 수학적 귀납법으로 보인다. 먼저 사람이 세 명 이하면 거의 트리비알.. 케바케. 네 명인 경우 선이 두 개 이하면 not connected이기 때문에 한 component vs 나머지로 만들면 적대관계로 만들 수 있음. 선이 세 개라면 가능한 경우는 삼각형이거나 한 명에게 세 명이 연결된 경우. 삼각형은 삼각형 vs 나머지 한 점으로 놓으면 적대관계이고, 후자의 경우 중심 한 명 vs 나머지 세 명으로 놓으면 우호관계가 된다. 선이 네 개 이상이라면 차수가 3 이상인 점이 존재하게 되어 그 점 vs 나머지 세 점으로 하면 우호관계가 되는데 예외가 딱 하나. 4-cycle. 그런데 이 경우 1-2-3-4-1이라면 1,3 vs 2,4가 우호관계.

이제 n명일 때 성립함을 가정한다. 그리고 n+1명일 때를 본다. 한 점 아무거나 택하고 그걸 제외한 것들을 보면 귀납법 가정에 의해 둘로 나눠 서로 연결되거나 서로 연결되지 않게 할 수 있다. 이 한 점을 x라 하고 이 두 집합을 A,B라 하자. 만약 A,B가 적대관계라면 이 그래프에서 선이 있는 것을 없애고 선이 없었던 곳엔 선을 만든다. 그래도 문제의 조건이 그대로 성립한다! (왜냐면 문제의 조건이 의미하는건 어떤 네 점을 택했을 때 A-B-C-D이고 B-/D-/-A-/-C가 된다는 건데, 위의 시행을 해도 똑같은 상황이 되기 때문이다.) 따라서 A,B가 우호관계일 때만 체크하면 된다. (편의상 x-/-yx,y 사이에 선이 없음을 뜻하기로.)

이제 a \in A, b \in B가 있어 a-x-/-b이거나 a-/-x-b가 성립함을 보이자. 만약 그렇지 않다면 A vs \{ x \}B vs \{ x \}가 전부 우호관계이거나 전부 적대관계이다. 어떤 경우든 A \cup \{ x \} vs B로 하면 해결됨. 이제 일반성을 잃지 않고 a -/- x-b라 하자.

B에서 x와 연결된 것들의 집합을 B_1, 나머지를 B_2라 하자. 앞에서 얻은 결과는 B_1이 공집합이 아니라는 것이다. 그러면 임의의 b_1 \in B_1, b_2 \in B_2에 대해 x-b_1-a-b_2인데 x-/-a,x-/-b_2이므로 b_1-b_2여야 한다. 따라서 B_1,B_2는 우호관계. 그러면 A \cup B_2 \cup \{ x \} vs B_1로 하면 된다.

따라서 수학적 귀납법으로 된다.

(b) 조금 서술이 까다로운데.. 디테일은 생략하기로 한다.

주요 키 포인트는, 주어진 조건을 만족하는 그래프에서 subgraph, 즉 점 집합의 부분집합을 잡고 원래 변 집합에서 이 점의 부분집합에 점을 갖는 것만 남긴 그래프를 보면 이것도 원래 조건을 만족한다는 것이다. (원래 조건 자체가 임의의 4-subgraph에 대해서 보는 intrinsic (?)한 조건이었기 때문에..) 그러면 (a)에 의해 우호나 적대 관계의 AB로 나눌 수 있다. 이를 A-B로 쓰자. 그러면 A,B 각각이 또 조건을 만족시키기 때문에 AA_1-A_2로, BB_1-B_2로 나눌 수 있다. 이를 (A_1-A_2)-(B_1-B_2)로 쓴다. 또 B_1을 두 개로 나누어 B_{11},B_{12}로 나누면 (A_1-A_2)-((B_{11}-B_{12})-B_2)로 쓰고, … 계속 하면 등장하는 모든 집합이 원소가 1개인 것들로 바꿀 수 있다. 이 과정에서 마지막 과정에 주목한다. 마지막에는 어떤 집합 XX_1-X_2로 나눴을텐데, 지금까지 오면서 X_1,X_2는 둘 다 X에 속하면서 다른 집합들과의 연결상태가 전부 동일했다. 따라서 X_1,X_2는 자신들끼리를 제외하면 다른 것들과의 연결상태가 동일하게 됨. 끝.

아마 원래 문제를 내고픈건 (b)였을텐데, (b) 하나만 내면 문제가 너무 어려워지니 그 과정인 (a)를 추가한 것이 아닐지?

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

Finite Difference Method

미분 가능한 함수에서 미분이란 함수값의 변화량을 수치화한 것이다. 그렇다면 연속도 아닌 이산적인 함수에서 (즉, 정의역이 구간이 아니라 띄엄띄엄 떨어진 수들의 집합인 경우) 미분에 해당하는 것은 무엇일까? 논의는 여기에서 시작한다.

f\mathbb{Z}에서 정의되는 경우를 보자. 이 때 답은 단순하다. f(x+1)-f(x)f의 변화량을 나타낸다. 이제 Df(x)f(x+1)-f(x)로 정의하자. 즉 Df(x)라는 함수를 f(x+1)-f(x)로 바꾸는 함수의 변환이라 볼 수 있겠다. (마치 미분이 f(x)f'(x)로 바꾸듯)

그러면 D^nf(x)=\sum_{i=0}^n (-1)^{n-i} \binom{n}{i} f(x+i)가 성립한다. 증명이야 뭐.. 수학적 귀납법말곤 딱히.. 아무튼 이를 finite difference라 하고, 한국어로 어떻게 번역해야할지 고민한 끝에 차분법으로 명하기로 했다. (미분과 대조되는 개념으로, 차로 나눈다는 뜻의 差分) 그래서 차분법이란 이름으로 내가 쓴 책 “올림피아드 조합론”에도 실어버렸는데, 놀랍게도 일본어에서 똑같은 한자의 단어로 번역하고 있었다!

이제 특수한 경우, 즉 f가 다항수인 경우를 보자. 만약 f의 차수가 d이고 최고차항이 c_dx^d라 하자. 그러면 Df=c_d((x+1)^d-x^d)+\cdots인데 여기서 x^d는 전부 없어지고 x^{d-1}은 맨 첫 항에서만 나타나며 그 항은 dc_d x^{d-1}으로 계수가 0이 아니다. 따라서 차수는 정확히 1 줄어든다. 곧 D^nf(x)의 차수는 d-n이 된다. 곧 n=d이면 상수함수가 되고, n>d이면 0이 된다. 이를 다시 정리하면 다음과 같다.

n>d이면 \displaystyle \sum_{k=0}^n (-1)^k \binom{n}{k} f(k)=0이 성립한다.

실제론 f(k)가 아니라 f(x+k)인데, x만큼 옮기면 어차피 같은 함수니까 x=0인 경우만 state해줘도 상관이 없다.

사실 위의 정리는 다른 풀이가 많다. 다음은 그들을 간략히 설명한 것들.

First Solution. 앞의 풀이대로, D를 적용하면 차수가 하나씩 줄어들어서 성립.

Second Solution. 라그랑주 보간법. n=d+1일 때만 하면 그 이후는 자명한데, 그 때는 d+1개의 함수값이 주어지면 f를 결정할 수 있으므로 x=0,1,\cdots,d일 때를 대입한 결과들로 f를 구한 후 그에 x=d+1를 대입하면 얻을 수 있다. 방법만 알면 그 이후는 그저 계산일 뿐..

Third Solution. \binom{x}{i}i차 다항식으로, \binom{x}{0},\cdots,\binom{x}{n}n차 이하의 다항식들의 vector space over \mathbb{C}의 한 basis가 된다. 위 식에서 D^n(af+bg)=aD^nf+bD^ng이므로 \binom{x}{i}들에 대해서만 보이면 된다. 이는 \binom{n}{k}\binom{k}{i}=\binom{n}{i}\binom{n-i}{k-i}란 유명한 등식을 이용하면 증명이 된다.

Fourth Solution. 서인석 형님의 증명이다. 위와 같은 이유로 x^i에 대해서만 성립함을 보이면 되는데, \displaystyle \sum_{k=0}^n (-1)^k \binom{n}{k}k^ii개의 원소를 가진 집합에서 n개의 원소를 가진 집합으로 대응되는 전사함수의 개수와 같음을 포함과 배제의 원리로 보일 수 있다. 그러나 i \leq d <n이므로 그런 함수는 없으므로 이 값은 0이 된다.

저 정리를 이용하면 많은 문제들을 쉽게 증명하는 것이 가능하다. 먼저 조합등식들 중에 일부 문제들은 위의 내용을 응용하면 한 방에 증명이 된다. 그 예로 다음 문제를 본다.

p_1+p_2+\cdots+p_r<n을 만족하는 자연수 p_1,p_2,\cdots,p_r,n에 대하여 \displaystyle \sum_{k=0}^n (-1)^k \binom{n}{k} \binom{p_1+k}{k}\cdots \binom{p_r+k}{k}=0임을 보여라.

2003년 KMO 여름학교의 연습문제 중의 하나로 나온 문제. (출처가 더 있을 법한데 잘 모르겠다.) 책에는 모의고사라고 썼는데 오타..라기보다 헷갈렸다. 여튼, f(x)=\binom{p_1+x}{p_1} \cdots \binom{p_r+x}{p_r}로 잡으면 이 다항식의 차수가 p_1+\cdots+p_r<n이 되어 바로 대입하면 증명이 끝난다. 와우

이 문제의 별해도 있어 생성함수를 이용하여 증명할 수도 있고, 조합적인 해석을 할 수도 있다. 그러나 지금 너무 졸려져서 왠지 귀찮고.. 궁금하신 분들은 책을 참조하시길… (후에 귀차니즘에서 회복하면 다시 쓸 수도)

남은 문제들의 일부를 옮겨 적으면 다음과 같다.

1. (4th Mathlinks Contest) m \geq n일 때 \displaystyle \sum_{k=0}^n (-1)^k \binom{n}{k}\binom{m-k}{n}의 값을 구하여라.

2. (2008 Putnam) n \geq 3인 정수가 있다. 실계수 다항식 f,g가 있어 좌표평면에서 (f(1),g(1)),(f(2),g(2)),\cdots,(f(n),g(n))이 정n각형의 점들을 반시계방향으로 나열한 것이 되게 한다. 이 때 f,g중 적어도 하나는 차수가 n-1 이상임을 보여라.

3. (1983 IMO Short-list) F_1=F_2=1인 피보나치 수열 F_n이 있다. k=992,993,\cdots,1982일 때 P(k)=F_k를 만족하는 차수 990인 다항식 P에 대해 P(1983)=F_{1983}-1임을 보여라.