Posts Tagged ‘ 모의고사 ’

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이란 개념을 쓰고 있더라. 현역 시절에도 사영기하 쪽은 하나도 안 들여다보았고 지금도 생소한 개념이라 읽기가 꺼려진다. 그래도 언젠가 한 번 봐야지..

논증 풀이 환영.

2009 KMO 겨울학교 모의고사 2차 조합부등식

다음은 2009년 1월에 있었던 KMO 겨울학교의 모의고사 2차에 나온 문제이다.

n>=0인 정수에 대해, \sum_{i+j+k=n} \frac{(3i)!}{i!^3}\frac{(3j)!}{j!^3}\frac{(3k)!}{k!^3} \leq 27^n임을 보여라.

생긴게 참 조합적으로 의미도 있어 보이고, 실제로 작은 n 몇 개 대입하면 갭이 크기 때문에 조합적으로 쉽게 증명이 되리라 생각되어도 잘 안 된다.

풀이는 생성함수를 이용한다. \frac{1}{(1-27x)^{1/3}}\sum_{n \geq 0} \frac{(3n)!}{(n!)^3}x^n을 비교하자. 좌변은 Newton 이항 정리를 이용한다. 그 식은 (1-27x)^{-1/3}이므로
\displaystyle \sum_{n \geq 0} \binom{-1/3}{n}(-27x)^n=\sum_{n \geq 0}\frac{(-\frac{1}{3})(-\frac{4}{3})\cdots(-\frac{3n-2}{3})}{n!}(-27)^nx^n
\displaystyle = \sum_{n\geq 0} \frac{1 \cdot 4 \cdot \cdots \cdot (3n-2)}{n!}9^n x^n
\displaystyle \geq \sum_{n\geq 0} \frac{(3n)!}{n!(3 \cdot 6 \cdot \cdots \cdot 3n)^2}9^nx^n
\displaystyle =\sum_{n\geq 0} \frac{(3n)!}{(n!)^3}x^n이 된다. 즉 \frac{1}{(1-27x)^{1/3}}x^n의 계수를 a_n, \sum_{n \geq 0} \frac{(3n)!}{(n!)^3}x^nx^n의 계수를 b^n이라 하면 a_n \geq b_n이 성립한다.

따라서 \displaystyle \left( \sum_{n \geq 0} \frac{(3n)!}{(n!)^3}x^n \right)^3의 계수는 \displaystyle \sum_{i+j+k=n}a_ia_ja_k이고 \displaystyle \left( \sum_{n \geq 0} \frac{(3n)!}{(n!)^3}x^n \right)^3의 계수는 \displaystyle \sum_{i+j+k=n}b_ib_jb_k이므로 \displaystyle \left( \sum_{n \geq 0} \frac{(3n)!}{(n!)^3}x^n \right)^3의 계수, 즉 주어진 식의 우변이 \displaystyle \sum_{i+j+k=n}a_ia_ja_k의 계수, 즉 주어진 식의 좌변보다 크거나 같다. 이로써 증명이 끝난다.

아직 조합적 풀이는 찾지 못했다.

이 부등식의 갭은 상당히 커서, 사실 \displaystyle \lim_{n \rightarrow \infty}\frac{(LHS)}{(RHS)}=0인 것도 증명이 가능하다. 이는 위의 풀이에서 조금만 더 연구하면 나오는 결과로, 원래 내가 이 문제를 모의고사에 낼 때엔 위의 문제만 냈는데 후배가 이를 개조해서 얻은 결과인 위의 리미트 문제를 part b로 추가해서 냈다. (중등부 모의고사엔 part a만이 나왔다.)

이 문제는 이미 알려진 다음 문제의 analogue이다.

n \geq 0인 정수에 대해, \displaystyle \sum_{i+j=n} \frac{(2i)!}{(i!)^2}\frac{(2j)!}{(j!)^2} = 4^n임을 보여라.

이 문제 역시 위에서 보인 방법과 똑같이 풀린다. 이 때엔 \frac{1}{\sqrt{1-4x}}의 계수를 구하면 그것이 \binom{2n}{n}이 됨을 보이면 된다.

이 등식의 경우 조합적인 풀이가 있다. (찾아내는 것은 다소 힘들긴 하지만, 풀이 자체는 간단하다.) 그 풀이는 다음과 같다. 먼저 (0,0)에서 북동쪽↗과 남동쪽↘으로 2n번 이동하는 경로들을 생각하자. 자유롭게 움직여도 된다. 그러면 매번마다 두 번의 선택이 있으므로 경우의 수는 총 2^{2n}=4^n이다. 한 편, 이 경로가 x축과 마지막으로 만나는 곳을 (2(n-k),0)이라 하자. (x좌표가 짝수임은, 움직일 때마다 y좌표의 기우성이 달라지는데 처음과 마지막이 둘 다 0이면 움직인 횟수가 짝수번이어야하기 때문이다.) 그러면 시작부터 (2(n-k),0)까지 움직이는 횟수는 45도 돌려서 생각하면 (0,0)에서 (n-k,n-k)까지 오른쪽과 위쪽으로 움직이는 경우의 수가 되어 \binom{2(n-k)}{n-k}이다. 그럼 이제 보여야할 사실은 하나다. (2(n-k),0)에서 (혹은 그냥 (0,0)에서) 2k번 움직이되 x축에 닿지 않는 경우의 수가 \binom{2k}{k}임을 보이면 된다.

이를 45도 돌려서 생각하면, (0,0)에서 2k번 움직이되 y=x와 닿지 않게 움직이는 경우의 수가 \binom{2k}{k}임을 보이는 것이 된다. 맨처음에 위로 올라갈 수도 있고 오른쪽으로 갈 수도 있으니 한 경우를 보아 2를 곱한다. 일반성을 잃지 않고 y=x 밑으로 움직이는 경우의 수를 생각하자. 그러면 이 상황을 x축 방향으로 -1만큼 움직이면 y=x 이하로 (이번엔 닿아도 된다) 2k-1번 움직이는 경우의 수가 된다. 그 마지막 점은 (k,k-1),(k+1,k-2),\cdots,(2k-1,0)이 되는데 그 중 하나 잡아 (k-1+i,k-i)로 가는 경우의 수를 세자.

방법은 카탈란 수열을 계산하는 조합적 방법와 동일하다. y=x를 넘는 경우 최초로 넘게 되는 곳을 (a,a+1)라 할 때 그 이후의 결과는 y=x+1에 대해 대칭해버리면 그 결과는 (0,0)에서 (k-i-1,k+i)로 가는 경로가 되며, 임의의 이런 경로는 반드시 y=x를 넘어야 하므로 또 최초로 넘는 순간에 대해 그 이후를 y=x+1에 대해 대칭시키면 원래 조건을 만족시키는 경로가 된다. 따라서 그 경우의 수는 \binom{2k-1}{k+i}가 된다. 곧 원래 조건을 만족시키는 경우의 수는 \binom{2k-1}{k-1+i} -\binom{2k-1}{k+i}이 된다.

따라서 y=x 밑으로 2k-1번 움직이는 총 경우의 수는 \displaystyle \sum_{i=1}^k \left( \binom{2k-1}{k-1+i} -\binom{2k-1}{k+i} \right) = \binom{2k-1}{k}가 된다. (마지막 항의 \binom{2k-1}{2k}는 0으로 친다. 실제로 위의 과정에서 생각해도 0이어야 하고.) 따라서 총 경우의 수는 2\binom{2k-1}{k}=2\binom{2k-1}{k-1}=\binom{2k}{k}이다. 이로써 이 조합등식이 증명된다!

물론 맨 처음의 문제를 만들게 된 계기는 이 문제였다. 매우 단순한 일반화.