Posts Tagged ‘ 여름학교 ’

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

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

챕터 미리보기!

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

파일: 조합등식 강의록

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 KMO 여름학교 모의고사 2차 #1

그동안 이것저것 일이 많아서 너무 오래 손을 놓고 있었다. 이번에 여름학교에 갔을 때가 마친 모의고사 보기 전이었기에 몇 문제를 propose했고 일부는 모의고사로 출제되었다. 다음은 그 중 한 문제.

예각 부등변 삼각형 ABC에 대해 A에서 BC에 내린 수선의 발을 P라 하고, BC,CA,AB의 중점을 각각 D,E,F라 하자. 그리고 P에서 DE,DF에 내린 수선의 발을 연결한 직선을 l_a라 하자. 마찬가지로 l_b,l_c를 정의하면 l_a,l_b,l_c는 한 점에서 만남을 보여라.

사실 이 문제 논증으로 풀려고 하면 의외로 어렵다. 나도 논증 풀이는 잘 모르겠다. 단지 확실한 것은 해석 기하 풀이가 길지 않게 반드시 존재하기 때문에 너무 어려운 포지션으로 나오기도 힘들다는 것이었다. 그래서 1번으로 냈는데, 별로 평균 점수는 그렇게 높지 않게 나타난 것 같다고.

당시 문제를 감수했던 L이 논증 풀이를 하나 제시하긴 했는데, 다소 복잡했던 것 같아 신경을 못 썼다. 매쓰링크에 올려보니 논증풀이가 올라오긴 왔는데 orthopole이란 개념을 쓰고 있더라. 현역 시절에도 사영기하 쪽은 하나도 안 들여다보았고 지금도 생소한 개념이라 읽기가 꺼려진다. 그래도 언젠가 한 번 봐야지..

논증 풀이 환영.

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

예전에 매쓰링크의 블로그에다 썼던 글을 번역. 처음이자 마지막으로 계절학교 조교를 했던 2005년 여름학교에서 모의고사 용으로 두 문제를 만들어 한 문제는 중등부 2차 1번, 한 문제는 고등부 2차 5번에 냈는데 둘 다 학생 총점이 14점을 넘기지 못한 일화가 있다. 이 사실을 발견한 것은 고등학교 재학 중이던 2004년이었는데 당시엔 풀지 못했다가 후에 풀이를 발견하여 문제화하였다.

가끔 대칭 부등식을 풀 때에 주어진 변수들의 symmetric sum, 즉 대칭 합을 이용하여 식을 표현하는 것이 유용한 경우가 있다. 이는 항상 가능한 일로, 대칭 식은 반드시 “기본적인” 대칭 합들로 표현이 가능하기 때문이다. 여기에서 일컫는 대칭 합은 S_{i}=\frac{t_{n-i}}{\binom{n}{i}}으로 여기서 t_{k}(x+x_{1})(x+x_{2})\cdots(x+x_{m})에서의 x^{k}의 계수이다.

이 대칭 합들에 관한 유명한 부등식 두 개가 알려져있다.
Newton’s inequality 1 \leq k \leq m-1이면 S_{k}^{2}\geq S_{k+1}S_{k-1}가 성립한다.
Maclaurin’s inequality 0 \leq a< b \leq m이면 S_{a}^{b}\geq S_{b}^{a}가 성립한다.
Maclausin의 부등식은 산술기하 평균 부등식의 일반화이기도 하다. (a=1,b=n)

이제 이 부등식들을 하나의 부등식으로 일반화를 하자. 이를 위해 볼록성과 majorization과 연관된 강력한 부등식인 Karamata’s inequality (혹은 majorization inequality) 를 이용한다.
Majorization inequality 만약 구간 I 내에서 (a_{1},\cdots,a_{n})(b_{1},\cdots,b_{n})를 majorize하면 I에서 볼록인 함수 f에 대해 \sum_{i=1}^{n}f(a_{i}) \geq \sum_{i=1}^{n}f(b_{i})가 성립한다.
이 부등식의 증명의 주요 키 포인트는 아벨 합을 이용하는 것이다. 이에 대한 증명은 Mathlinks에서도 찾아볼 수 있다. (후에 한 번 글을 올릴까 한다.)

이제 만약 \ln{S_i}들이 마치 “볼록”하거나 “오목”한 것처럼 행동한다면 비슷한 결과를 얻을 수 있어야 한다. 실제로 majorization inequality의 증명은 구간 I의 연속적인 값들을 이용하는 것이 아닌 이산적인 값들을 이용하기 때문에 비록 S_i의 “변수” i가 이산적이어도 비슷하게 적용하는 것이 가능하다. 따라서 \ln{S_i}들이 볼록한지 오목한지만 확인하면 되는데, 이것은 Newton 부등식의 직접적인 결과이다. 왜냐면 Newton 부등식 자체가
2ln S_{k}\geq ln S_{k+1}+ln S_{k=1}, 즉 \ln{S_i}의 오목성을 뜻하기 때문이다. 따라서, 우리는 다음과 같은 부등식을 얻는다.

0 이상 m 이하인 정수 a_{i},b_{i}에 대해 만약 (a_{1},a_{2},\cdots,a_{n})(b_{1},b_{2},\cdots,b_{n})을 majorize하면 \prod_{i=1}^{n}S_{a_{i}}\leq \prod_{i=1}^{n}S_{b_{i}}가 성립한다.

왜 이것이 앞의 두 부등식의 일반화일까? 이유는 간단하다. (k+1,k-1)(k,k)를 majorize하는 것에서 Newton’s inequality를 얻을 수 있고, a < b일 때 (b,b,\cdots,b,0,\cdots,0)(a,a,\cdots,a)를 majorize한다는 것에서 Maclaurin’s inequality를 얻을 수 있기 때문이다.

등호조건을 따지는 것은 그리 어렵지 않으니 직접 확인해보길 바란다. (딱히 우리의 예상을 빗나가진 않는다.)