Posts Tagged ‘ KMO ’

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

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

챕터 미리보기!

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

파일: 조합등식 강의록

2010 KMO #8

이차잉여인간과 함께하는 이차잉여 문제!

8. 원탁에 2010명의 사람이 둥글게 앉아 있다. 어떤 사람에게 과자를 주고, 그 사람으로부터 시계방향으로 1번째, 1+2번째, 1+2+3번째, …, 1+2+…+2009번째 사람에게 과자를 주었다. 이 때, 과자를 하나 이상 받은 사람의 수를 구하여라.

이런 문제도 예전에 어디선가 봤었는데..

각설 답은 408개. 사실 이런 문제는 2010 대신 더 작은 수를 대입해서 앞에 몇 개 좀 해보면 바로 감이 잡히기 마련. mod 2010으로 \frac{n(n+1)}{2}들이 총 몇 개 나오는지를 구하는 문제이다. 이들은 \frac{n(n+1)}{2} = \frac{(2n+1)^2-1}{8}이므로 홀수의 제곱수들과 연관이 깊다.

먼저 mod 1005로 이차잉여가 몇 개있는지를 본다. 이건 중국인의 나머지 정리가 해결해준다. 다행히도 1005는 홀수인 소수들의 곱으로 무승수이다. (3, 5, 67의 곱) 홀수의 소수에 대해선 이차잉여가 어떻게 나오는지 잘 안다. 구체적으로 p가 홀수인 소수이면 이차잉여\frac{p+1}{2}개가 나온다. 그러면 서로 다른 홀수 소수 p,q에 대해 mod pq이차잉여는 몇 개인가? \frac{p+1}{2}\frac{q+1}{2}가 된다. 왜냐면 먼저 pq에 대해 이차잉여인 것은 mod p나 mod q로 봐도 이차잉여가 되어야 하고, 역으로 mod p이차잉여 하나 택해 x라 하고 mod q이차잉여 하나 택해 y라 하면 a^2 \equiv x\text{ (mod }p\text{)}, b^2 \equiv y\text{ (mod }q\text{)}a,b를 찾을 수 있고, 그러면 c \equiv a\text{ (mod }p\text{)}, c \equiv b\text{ (mod }q\text{)}c를 mod pq에서 찾으면 x,y에 해당되는 mod pq의 이차잉여를 찾을 수 있기 때문이다. 마찬가지로 생각하면, mod 1005로 이차잉여의 개수는 2 \cdot 3 \cdot 34=204개가 된다.

한 편, 홀수 k에 대해 mod k이차잉여 개수를 q라 하자. (현재 k=1005, q=204) 그러면 우리가 관심있는 것은 홀수인 이차잉여 mod 2k이므로 x^2 \equiv 1\text{ (mod }2\text{)}x^2 \equiv 0^2,1^2,\cdots\text{ (mod }k\text{)}의 해를 찾으면 되는데 앞의 것의 해는 x \equiv 1\text{ (mod }2\text{)}밖에 없으므로 개수는 그냥 q가 된다. 그럼 이런 홀수 제곱수들에서 1을 뺀 후 8로 나눈 것들을 봐야하는데, 1로 빼면 짝수들 mod 2k이고, 2로 먼저 나누면 어떤 수들 mod k가 된다. (not 2k) 그러면 하나 더 확인해줘야할 사실은 임의의 a에 대해 \frac{a(a+1)}{2} \equiv k+ \frac{b(b+1)}{2}\text{ (mod }2k\text{)}b가 존재하겠냐는 것. 그런 b2k-a-1로 넣으면 된다.

즉, 각각의 홀수 이차잉여 mod 2k마다 1을 빼주고 2로 나누면 그 값들은 mod k로 총 q개가 나오고, 이를 mod 2k로 볼 때에 각각의 수들은 그 수와 그 수에 k를 더한 것 모두 나오게 되어 총 개수는 2q가 된다. 따라서 답은 2q=408.

깔끔하고 좋은 문제이긴 한데, 어디서 봤던 것 같은데 흠..

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

6. 원에 내접하는 사각형 ABCD에 대하여 직선 ABCD가 점 X에서 만난다. 점 B를 지나고 직선 AC와 직교하는 직선과 점 C를 지나고 직선 BD와 직교하는 직선의 교점을 P라 하고, 점 D를 지나고 직선 AC와 직교하는 직선과 점 A를 지나고 직선 BD와 직교하는 직선의 교점을 Q라 하자. 세 점 X,P,Q가 한 직선 위에 있음을 보여라.

X를 중심으로 하고 적당히 확대/축소하여 각 X의 이등분선에 대해 대칭하면 B,CD,A로 대응되도록 할 수 있다. 이 때 A,D가 각각 XC,XB 위의 점 A',D'로 대응된다고 하자. 그리고 P가 대응되는 점을 P'라 하자. 그러면 P'A,D에서 DD',AA'에 내린 수선의 교점이다.각을 따져보면 ACDD'가 평행이고 AA',BD가 평행임을 쉽게 확인할 수 있다. 즉 AP'DD'와 수직인데 DQAC와 수직이 되어 AP',DQ는 평행이다. 마찬가지로 DP',AQ도 평행이다. 따라서 AP'DQ는 평행사변형이 된다.

따라서 싸인 정리에 의해 \frac{AP'}{\sin \angle AXP'} = \frac{XP'}{\sin \angle XAP'} = \frac{XP'}{\sin \angle XDP'} = \frac{DP'}{\sin \angle DXP'}가 된다. (\angle XAP' = \frac{\pi}{2}-\angle{DD'A} = \frac{\pi}{2}-\angle{DA'A}=\angle P'DX as directed angles) 마찬가지로 \angle XAQ = \angle XDQ임을 이용하면 \frac{\sin \angle DXQ}{DQ} = \frac{\sin \angle AXQ}{AQ}가 되므로 \frac{\sin \angle AXP'}{\sin \angle DXP'} = \frac{\sin \angle DXQ}{\sin \angle AXQ}가 되어 \angle AXP'=\angle DXQ인데 P'P를 확대/축소하여 대칭시켰으므로 \angle AXP' = \angle DXP이다. 따라서 \angle DXP = \angle DXQ가 되어 X,P,Q는 일직선 위.

이 아이디어 쓴게 2009 쇼트에도 있었는데..

2010 KMO #5

내 기억엔 이거 예전 전국 기출문제인데..

5. 양의 실수 x,y,zx+y+z=1을 만족할 때, 다음 부등식이 성립함을 보여라.
\sqrt{\frac{x}{1-x}} + \sqrt{\frac{y}{1-y}} + \sqrt{\frac{z}{1-z}} > 2

매우 단순한 차수 맞추기를 하면 \sum \sqrt{\frac{x}{y+z}} \geq 2를 증명한 후 등호가 성립되지 않음을 보이면 된다. 그런데 \sqrt{\frac{x}{y+z}} \geq \frac{2x}{x+y+z} \Leftrightarrow x+y+z \geq 2 \sqrt{x(y+z)}가 산술기하 부등식으로 성립하고 다 더하면 바로 끝. 등호가 성립하려면 x+y=z,y+z=x,z+x=y가 성립해야 하는데 양의 실수에선 그럴 수 없으므로 모순이다.

그나저나 올해는 부등식이 두 개네.. 허허

+ 만약 음 아닌 실수도 용인하되 분모만 0이 안 되게 한다면 등호조건은 존재한다. 그러면 저 등호 조건이 x+y=z or z=0으로 되기 때문에 전체 등호조건은 x=y,z=0 등이 가능하게 된다. 이렇게 x=y=z 꼴이 아닌 등호조건 때문에 어려워진 문제. 또한 이렇기 때문에 우변의 2는 최선의 값이다. 왜냐하면 양의 실수에선 x=y, z \rightarrow 0으로 만들면 좌변의 값이 2로 수렴하므로..

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

3. 삼각형 ABC의 내접원 I가 변 BC,CA,AB와 각각 P,Q,R에서 접한다고 하자. 두 점 B,C를 지나는 원이 원 I와 점 X에서 접하고, C,A를 지나는 원이 I와 점 Y에서 접하고, A,B를 지나는 원이 점 Z에서 접할 때, 세 직선 PX,QY,RZ가 한 점에서 만남을 보여라.

다소 계산이 많이 포함된 증명. 좀 아쉽군.. 분명 더 깔쌈한 증명이 있을 법 한데.

먼저 내접원을 \gamma, 잡은 세 원을 각각 \gamma_a,\gamma_b,\gamma_c라 한다. 그리고 직선 PX\gamma_aBC에 대해 A의 반대쪽에서 만나는 점을 잡아 M_a라 하면 M_a가 호 BC의 중점이 됨은 잘 알려져 있다. 원 \gamma_a의 중심을 O_a, 반지름을 R_a라 하자. 내접원의 반지름 길이는 r. 그러면 IO_a = R_a-r이다. I,O_a에서 BC에 내린 수선의 발을 임의로 H_1,H_2라 하면 H_1H_2=\frac{b-c}{2}이다. 이건 b=c여도 다 통용되는 이야기. 그러면 O_aH_2=\sqrt{R_a^2-\frac{a^2}{4}}이므로 피타고라스의 정리에 의해 (R_a-r)^2 = \frac{(b-c)^2}{4} + (r+\sqrt{R_a^2 - \frac{a^2}{4}})^2가 성립하고 정리하면 \frac{a^2-(b-c)^2}{8r} = R_a + \sqrt{R_a^2 - \frac{a^2}{4}}가 된다. (참고로 이것은 O_aBC에 대해 A의 반대쪽에 있을 때인데, 그 외의 경우는 중간 중간 부호만 바꿔주면 되고 겨과는 같다. 아마 그런 경우는 없던 것 같던데, 계산에 실수를 했을 수도 있어서..)

자 그러면 M_aO의 길이를 구하자. 여기서 OABC의 외심이다. 이는 M_aH_2 + H_2O = R_a + \sqrt{R_a^2 - \frac{a^2}{4}} + R \cos A인데 정리하면
\displaystyle \frac{a^2-(b-c)^2}{\frac{16S}{a+b+c}} + \frac{abc}{4S}\frac{-a^2+b^2+c^2}{2bc}
\displaystyle \frac{-a^3-b^3-c^3+a^2b+a^2c+b^2c+b^2a+c^2a+c^2b+2abc}{16S}가 된다. (SABC의 넓이) 즉 a,b,c에 대한 대칭식이 되므로, M_aO=M_bO=M_cO가 된다. 이는 M_aM_bM_c의 외접원은 O를 중심으로 하며, \gamma_a,\gamma_b,\gamma_c와 접함을 의미한다.

이제 M_a에서의 \gamma_a의 접선을 잡고 마찬가지로 나머지 두 접선을 잡는다. 그러면 이들은 ABC의 변들과 평행하므로 이 세 직선으로 이루어진 삼각형은 ABC와 닮음이다. 게다가 대응변이 평행하므로 닮음의 중심이 존재한다. 그런데 이 큰 삼각형의 내접원이 바로 M_aM_bM_c의 외접원이고 이것이 변과 접하는 점은 M_a이고, ABC에서 내접원이 변과 접하는 점은 P이다. 즉 P,M_a는 닮음 변환으로 대응되는 점이다. 따라서 닮음의 중심을 K라 하면 K,P,M_a가 한 직선 위에 있게 된다. 마찬가지로 K는 직선 QM_b,RM_c 위에 있게 되는데 이 직선들이 바로 PX,QY,RZ이므로 증명이 끝난다.

뒷부분은 그나마 깔끔..