Archive for July, 2010

1986 IMO Short-list 기하 문제와 관련 부등식

원래 1986년 쇼트리스트 문제 중에 다음과 같은 문제가 있었다.

삼각형 ABC의 외심을 O, 내심을 I, 내접원과 세 변의 접점을 D,E,F, 삼각형 DEF의 구점원의 중심을 X라 하자. O,I,X가 일직선 위에 있음을 증명하여라.

이 문제에서 조금 더 나아가 길이를 비교하여 다음 기하 부등식을 얻어낼 수 있다. (정확히는 그 길이의 비를 구할 수 있다.) 대략 2006년 쯤에 발견한 결과로 기억한다.

OI \geq 4IX임을 보여라.

앞의 문제를 (a), 뒤의 문제를 (b)라 한다.

First Solution. (a) 삼각형 DEF에서 외심이 I이고 구점원의 중심이 X이므로, 무게중심을 G라 하면 IX=\frac{3}{2}IG이며 I,X,G는 일직선 위에 있다. 이제 O,I,G가 일직선 위에 오며 OI \geq 6IG임을 보이자.
\vec{OA}=\vec{a}이라 하고 나머지도 마찬가지로 정의한다. \vec{OI}=\sum \frac{a}{a+b+c}\vec{a}이며 \vec{OG}=\frac{1}{3}(\vec{OD}+\vec{OE}+\vec{OF})=\frac{1}{3}\sum \frac{s-c}{a}\vec{b}+\frac{s-b}{a}\vec{c}=\sum \frac{1}{3}(\frac{s-b}{c}+\frac{s-c}{b})\vec{a}이고 \vec{0}=\sum \sin{2A} \vec{a}이므로 O,I,G가 일직선 위에 있음을 보이기 위해 \vec{OG}\vec{OI}의 스칼라 배수임을 보이면 되고, 그를 위해 \vec{OG}+k\vec{0}=l\vec{OI}가 되는 상수 k,l이 존재함을 보이면 된다. 여기서 la,b,c에 대한 대칭식이 될 것이므로, \vec{OG}+k\vec{0}\vec{OI}\vec{a}의 계수의 비율이 l, 즉 대칭식이 되게 하는 대칭식 k를 잡으면 된다. 그 비율은 \displaystyle \frac{\frac{1}{3}(\frac{s-b}{c}+\frac{s-c}{b})+k\sin{2A}}{\frac{a}{a+b+c}}이므로 이를 계산하자.

\displaystyle \frac{\frac{1}{3}(\frac{s-b}{c}+\frac{s-c}{b})+k\sin{2A}}{\frac{a}{a+b+c}}
\displaystyle = \frac{a+b+c}{3}\frac{\frac{s-b}{c}+\frac{s-c}{b}+3k\sin{2A}}{a}
\displaystyle = \frac{a+b+c}{3abc}(b(s-b)+c(s-c)+3kbc\sin{2A})이므로, \vec{b}의 계수는 \displaystyle \frac{a+b+c}{3abc}(a(s-a)+c(s-c)+2kac\sin{2B})이므로 두 값이 로 같음은 곧 \displaystyle b(x-b)+c(s-c)+3kbc\sin{2A}=a(s-a)+c(s-c)+3kac\sin{2B}임과 동치이다. 여기에서 3kc(b\sin{2A}-a\sin{2B})=a(s-a)-b(s-b)=(a-b)s-(a-b)(a+b)=-(a-b)(s-c)가 되어
\displaystyle k=\frac{-(a-b)(s-c)}{3c(b\sin{2A}-a\sin{2B})}=\frac{-(a-b)(s-c)}{6bc\frac{a}{2R}\frac{-a^2+b^2+c^2}{2bc}-6ac\frac{b}{2R}\frac{a^2-b^2+c^2}{2ac}}
\displaystyle =\frac{2R}{3}\frac{-(a-b)(s-c)}{-(a-b)(a+b)^2+(a-b)c^2} = \frac{2R}{3}\frac{s-c}{(a+b+c)(a+b-c)}=\frac{R}{3(a+b+c)}가 된다. 따라서 대칭식이 되어 증명이 끝난다.

(b) 앞의 결과에서 k=\frac{R}{3(a+b+c)}를 대입하자. 그러면
\displaystyle l=\frac{a+b+c}{3abc}(b(s-b)+c(s-c)+\frac{R}{a+b+c}2bc \sin{A} \cos{A}) = \frac{a+b+c}{3abc}(b(s-b)+c(s-c)+\frac{R}{a+b+c}\frac{a}{2R}(-a^2+b^2+c^2))
\displaystyle = \frac{1}{6abc}(-\sum_{cyc}a^3+\sum_{sym}a^2b+4abc)=\frac{1}{6abc}((-a+b+c)(a-b+c)(a+b-c)+6abc)
이다. 곧 \displaystyle \frac{OG}{OI}=\frac{(-a+b+c)(a-b+c)(a+b-c)}{6abc}+1이므로 \displaystyle \frac{IG}{OI}=\frac{(-a+b+c)(a-b+c)(a+b-c)}{6abc}가 된다. IX=\frac{3}{2}IG임에서 \displaystyle \frac{IX}{OI}=\frac{1}{4}\frac{(-a+b+c)(a-b+c)(a+b-c)}{abc} \leq \frac{1}{4}가 되어 OI \geq 4IX가 성립한다.

Second Solution. (a) 내접원과 BC,CA,AB의 접점을 D,E,F라 하자. 그리고 EF,FD,DE의 중점을 각각 P,Q,R이라 하자. 그러면 XPQR의 외심이다. 삼각형 AEF는 이등변 삼각형이므로 A,P,I는 한 직선 위에 있게 된다. (I는 내심으로 각 A의 이등분선 위에 있음) 이 때 \angle{APF}=\angle{AFI}=\frac{\pi}{2}이고 \angle{PAF}=\angle{FAI}이므로 삼각형 PAF와 삼각형 FAI는 닮음이다. 따라서 IP:IF=IF:IA, 즉 IA \cdot IP=IF^2이다. 이 때 내접원의 반지름의 길이를 r이라 하면 IA \cdot IP=r^2이다. 마찬가지로 IB \cdot IQ = IC \cdot IR = r^2임을 얻을 수 있으므로, 이 평면을 ABC의 내접원에 대해 반전하면 A \rightarrow P,B\rightarrow Q,C \rightarrow R이 되므로 ABC의 외접원은 PQR의 외접원으로 반전된다.

한 편, 이 외접원을 반전할 때 원래의 중심을 O라 하면, 반전된 후의 도형인 원의 중심은 X가 된다. 원래의 원은 직선 OI에 대해 대칭이므로 그 반전 역시 직선 OI의 반전, 즉 직선 OI에 대해 대칭이어야 한다. 따라서 X가 직선 OI 위에 있어야 하고 이는 O,I,X가 일직선 위에 있음을 증명하는 것이 된다. 이로써 증명은 끝난다.

(b) 직선 OI 위에서 생각하자. 이 수직선 위에서 I의 좌표를 0이라 하면 O의 좌표는 OI=\sqrt{R^2-2Rr}가 된다. 곧 외접원의 지름 양 끝점은 \sqrt{R^2-2Rr} \pm R이 되어 원 X의 지름 양 끝점은 \frac{r^2}{\sqrt{R^2-2Rr} \pm R}가 된다. 따라서 X의 좌표는 \displaystyle \frac{1}{2}(\frac{r^2}{\sqrt{R^2-2Rr}+R}+\frac{r^2}{\sqrt{R^2-2Rr}-R})=-\frac{r}{2R}\sqrt{R^2-2Rr}이 되므로 \frac{IX}{OI}=\frac{r}{2R} \leq \frac{1}{4}가 되어 증명된다.

Third Solution. OI^2 \geq 16IX^2를 보인다. 삼각형 DEF의 수심을 H이라 하면 구점원의 중심은 IH의 중점이다. IH^2=9r^2-(DE^2+EF^2+FD^2)이므로 IX^2=\frac{1}{4}(9r^2-\sum DE^2)이다. DE=2r \cos \frac{C}{2}이므로
\displaystyle 16IX^2 = 4(9r^2-4r^2(\sum \cos^2\frac{A}{2}))=4(9r^2-4r^2 \sum \frac{1+\cos A}{2})
\displaystyle = 12r^2-8r^2 \sum cos A인데, \sum \cos A = 1+\frac{r}{R}이므로 16IX^2=12r^2-8r^2(1+\frac{r}{R})가 된다. 따라서
\displaystyle R^2-2Rr=OI^2 \geq 16IX^2
\displaystyle \Leftrightarrow R^2-2Rr \geq 12r^2 -8r^2(1+\frac{r}{R})
\displaystyle \Leftrightarrow R^3-2R^2r-4Rr^2+8r^3 \geq 0
\displaystyle \Leftrightarrow (R-2r)^2(R+2r) \geq 0
인데 이 부등식은 성립하므로, 원래 부등식이 성립한다.

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임을 보여라.

2010 FKMO #1

다음은 올해 3월 27일에 있었던 KMO 최종시험, 통칭 FKMO에서 1번으로 나온 문제이다.

삼각형 ABC의 내접원이 BC,CA,AB와 접하는 점을 각각 P,Q,R이라 하자. 삼각형 ABC의 넓이를 T, 둘레의 길이를 L이라 할 때 다음 부등식이 성립함을 보여라.
\displaystyle \left( \frac{AB}{PQ} \right)^3 + \left( \frac{BC}{QR} \right)^3 + \left( \frac{CA}{RP} \right)^3 \geq \frac{2}{\sqrt{3}}\frac{L^2}{T}

먼저 BC=a,CA=b,AB=c라 할 때 QR의 길이들을 구하자. 이는 s=\frac{a+b+c}{2}이라 할 때 AQ=AR=s-a이므로 QR=2(s-a)\sin{\frac{A}{2}}이다. 여기서 x=\frac{-a+b+c}{2}, y=\frac{a-b+c}{2},z=\frac{a+b-c}{2}라 하면 \displaystyle (LHS) = \sum_{cyc} \left( \frac{y+z}{2x \sqrt{\frac{yz}{(x+y)(x+z)}}} \right)^3가 된다.

이제 산술기하 평균 부등식을 적용하면 \displaystyle (LHS) \geq 3\prod_{cyc} \left( \frac{y+z}{2x \sqrt{\frac{yz}{(x+y)(x+z)}}} \right) = 3 \frac{(y+z)^2(z+x)^2(x+y)^2}{8x^2 y^2 z^2}가 된다. 한 편, \displaystyle (RHS)=\frac{2}{\sqrt{3}}\frac{4(x+y+z)^2}{\sqrt{xyz(x+y+z)}}이므로 \displaystyle 3 \frac{(y+z)^2(z+x)^2(x+y)^2}{8x^2 y^2 z^2} \geq \frac{2}{\sqrt{3}}\frac{4(x+y+z)^2}{\sqrt{xyz(x+y+z)}}임을 보이면 된다. 이를 정리하면 \displaystyle ((y+z)(z+x)(x+y))^2 \geq \frac{64}{3\sqrt{3}}(x+y+z)^{3/2}(xyz)^{3/2}이다.

이를 증명하기 위해 \displaystyle (y+z)(z+x)(x+y) \geq \frac{8}{3} (x+y+z)(xyz)^{2/3}임을 보이자. 이는 x,y,zx^3,y^3,z^3을 대입한 후에 정리하면 \displaystyle 3\sum_{sym}x^6y^3+6x^3y^3z^3 \geq 8\sum_{cyc}x^5y^2z^2가 된다. 이를 증명하자.

산술기하 평균 부등식, 혹은 Muirhead 부등식에 의해 \displaystyle \sum_{sym}x^6y^3z^3 \geq 2\sum_{cyc}x^6y^{3/2}z^{3/2}가 성립한다. 따라서 \displaystyle 6\sum_{cyc}x^6y^{3/2}z^{3/2}+6x^3y^3z^3 \geq 8\sum_{cyc}x^5y^2z^2임을 보이면 된다. 또 x,y,zx^2,y^2,z^2를 대입한 후 정리한 다음 양변을 2x^3y^3z^3으로 나누면 \displaystyle 3\sum_{cyc}x^9+3x^3y^3z^3 \geq 4\sum_{cyc}x^7yz가 되므로 이것만 보이면 된다.

이를 위해 산술기하 평균 부등식으로 먼저 x^9+x^9+x^3y^3z^3 \geq 3x^7yz임을 보인다. 여기에서 \displaystyle 2\sum_{cyc}x^9+3x^2y^2z^2 \geq 3\sum_{cyc}x^7yz임을 보일 수 있다. 여기에 \sum_{cyc}x^9 \geq \sum_{cyc} x^7yz가 산술기하 평균 부등식 혹은 Muirhead 부등식으로 성립하므로 더해주면 원하는 결과가 증명이 된다.

등호는 x=y=z, 즉 a=b=c이므로 삼각형 ABC가 정삼각형일 때 성립한다.

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}이다. 이로써 이 조합등식이 증명된다!

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

생성함수의 종류와 poset

얼마전에 다른 게시판에 쓴 글을 다시 옮김과 정리.

생성함수에는 두 종류가 있다는 것을 수학경시 했던 사람이라면 다들 알 것이다. 일반적인 생성함수 (Ordinary generating function) 그리고 지수 생성함수 (Exponential generating function) 이들이 그것이다. 이들은 쉽게 말하자면 \sum f(n)x^n\sum f(n)\frac{x^n}{n!}의 꼴을 갖고 있다. 그리고 우리가 접해온 수많은 조합적인 개체들은 이들과 연관되는 경우가 많았다.

하지만 사실은 이게 생성함수의 전부가 아니다. 적어도 이런 종류로 알려진 것이 세 종류는 더 있다. (그 중 하나는 엄밀히 종류가 무한개라고 할 수도 있겠다만..) 첫 번째로, q-analogue version이기도 한 \sum f(n)\frac{x^n}{(n)!}. 여기서 (n)!(1+q)(1+q+q^2)...(1+q+...+q^{n-1}), 즉 n!의 q-analogue이다. 이는 Eulerian generating function이라 불리우며, 주로 \mathbb{F}_q 위의 벡터 스페이스에서 무언가를 세는 문제와 관련이 깊다. 예를 들면, f(n)이 dimension이 n인 한 vector space over \mathbb{F}_q의 subspace 개수라고 할 때 \sum f(n)\frac{x^n}{(n)!} = (\sum \frac{x^n}{(n)!})^2가 된다.

두 번째로 Doubly-exponential generating function. \sum f(n)\frac{x^n}{n!^2}이다. 즉 분모만 n!^2로 바꿨다. 대충 예상했겠지만 이 경우 특수한 행렬들과 관련되는 경우가 많다. (약간의 어폐가 있긴 하다.) 예를 들어 f(n)n\times n 행렬 중 각 요소가 음 아닌 정수이며 행과 열의 원소의 합들이 각각 2일 경우의 수라 하면 \sum f(n)\frac{x^n}{n!^2} = \frac{e^{x/2}}{\sqrt(1-x)} 임을 얻는다. ㄷㄷ 그리고 이 경우 일반화가 가능하여 r-exponential generating function \sum f(n)\frac{x^n}{n!^r}을 생각하는 경우가 많다.

세 번째로 Chromatic generating function. \sum f(n)\frac{x^n}{q^{\binom{n}{2}}n!} 꼴이다. 이것은 n개의 점을 갖는 그래프와 연관이 깊다. (주로 거기서 q-1개의 색을 칠하는 경우) 예컨대 f(n)n개의 점을 가지며 acyclic한 (cycle이 없는) 유향 그래프의 개수라 하면 \sum f(n)\frac{x^n}{q^{\binom{n}{2}}n!} = (\sum (-1)^n \frac{x^n}{q^{\binom{n}{2}}n!})^{-1}을 얻는다.

정리하면, 약간 단순화시켜서 ordinary는 음아닌 정수와 관련되고, exponential은 set에, Eulerian은 vector space, doubly exponential은 서로 잘 연결되어진 두 set의 pair (그래서 특수 행렬과 연관됨), 그리고 chromatic은 그래프와 관련이 된다.

자.. 이쯤 되면 과연 생성함수의 형태는 이것들로만 제한되는지는 당연히 의심된다. 그리고 당연히 답은 부정적이다. 부정적(negative)이자 부정적(a number of solutions)이다. 그러면 이들을 한데 묶어 설명할 순 없을까? 이들은 너무 따로따로 논다. 그리고 각각이 특색이 있기에 이들을 unify할 이론은 없어보인다.

그런데 그게 실제로 일어났습니다.

이야기는 poset, 즉 partially ordered set의 이야기로 올라간다. 아마 수학을 전공하는 사람들이면 Zorn’s lemma 배우면서 한 번은 거칠 개념이다. 즉 집합의 원소들 중 일부 쌍에만 순서를 주는 개념인데, 조합론에서는 이에 관련된 이론이 하나의 branch를 이룰 정도로 연구가 많이 이루어져 있다. 그 중 다음과 같은 특징을 갖는 poset P를 binomial poset이라 부른다.

a. P는 locally finite이고 (interval만 보면 finite) \hat{0}을 가지며 (unique minimum element라 보면 됨) infinite chain을 갖는다.
b. 임의의 interval [x,y]=\{z:x \leq z \leq y \}은 graded이다. (즉 rank function을 줄 수 있다) 또한 interval [x,y]의 길이가 n이면 [x,y]n-interval이라 부르자.
c. 임의의 음 아닌 정수 n에 대해, 임의의 두 n-interval은 maximal chain의 개수가 B(n)으로 똑같다.
이 때 B(n)P의 factorial function이라 하자.

아 아까 전까진 알기 쉽게 풀어쓰는 것을 목표로 했는데 이 문단으로 모든게 틀어져버렸어….

아무튼 factorial function의 이름에서 예감할 수 있듯 이 B(n)은 일반적인 의미의 factorial, 즉 n!의 연장선에 있다. 그리고 binomial poset은.. 한 마디로 말하면, 이 poset의 임의의 같은 크기의 부분을 잡아도 (부분 = interval, 크기 = length) 그 부분에서의 특정 동등한 개체의 ‘개수’ (즉 maximal chain의 개수) 가 항상 일정하게 나타나는 존재란 뜻이다.

그러면 binomial poset의 직접적인 예를 들자.

(1) P=\mathbb{N} (음아닌 정수 집합) 그리고 일반적인 perfect order를 주면 B(n)=1
(2) P\mathbb{N}의 유한 부분집합의 poset으로 잡으면 (order는 inclusion) B(n)=n!
(3) P\mathbb{F}_q 위의 무한차원 벡터공간의 subspace들의 poset으로 잡으면 B(n)=(n)!
(4) P= \{(S,T):S,T \subset \mathbb{N}, |S|=|T| \}으로 잡고 (S,T) \leq (S',T') \Leftrightarrow S \subset S', T \subset T'으로 잡으면 B(n)=n!^2
(5) 귀찮아서 복잡해서 생략.. 아무튼 잘 잡으면 q^{\binom{n}{2}}n!

그러면 이 다섯 개의 예가 바로 앞에서 잡은 다섯 종류의 생성함수와 관련된다. 즉 적당한 binomial poset 하나만 잡으면, 그에 관련된 한 종류의 생성함수를 만들 수 있고, 만약 그 binomial poset이 조합적으로 해석 가능하다면 의미 있는 생성함수 한 종류가 탄생되는 것이다!

더불어, \binom{n}{i}와 비슷하게 \frac{B(n)}{B(i)B(n-i)}를 생각할 수 있고 이는 사실 n-interval [x,y]에서 rank가 i인 원소의 개수와도 같다. 이 때 A(n)=\binom{n}{1}로 잡으면 B(n)=A(n)A(n-1)\cdots A(1)이 된다. 즉 factorial function의 이름이 생각보다 훨씬 본질과 가깝단 이야기.

이에 관련되어 incidence algebra와 합쳐지면 재미있는 사실들이 정말 많은데.. incidence algebra를 언급하는 것은 또 한 세월이 걸리고. Mobius algebra도 한 세월이 걸리고. 아쉽지만 이쯤에서 접도록 한다. 궁금한 사람들은 한 번 (\sum \frac{x^n}{B(n)})^2 = \sum f(n)\frac{x^n}{B(n)}이라 할 때 f(n)이 무엇인지 생각해보라. 참고로 ordinary이면 f(n)=n+1이고 exponential이면 f(n)=2^n이다. (답을 이야기하자면 interval의 길이가 n일 때 그 interval의 원소의 개수이다. ordinary는 [0,n]의 원소 개수가 n+1이고, exponential은 [\emptyset,[n]]의 원소의 개수는 곧 [n]의 부분집합의 개수이니까 2^n이고, …)

그리고, 방금 잡은 예에선 sum x^n/B(n)에 2제곱을 한 것인데 k제곱하면 어떻게 될까? (set이라면 무려 제2종 스털링 수가 등장한다!) doubly-exponential case는? 흥미진진하지 않을 수 없다.

REFERENCE
R. Stanley, Enumerative Combinatorics, Ch.3

2009 IMO Short-list

작년 독일 IMO의 후보 문제.

ALGEBRA

A1. 다음 조건을 만족하는 최대의 정수 k를 구하여라: 2009개의 삼각형이 주어져 있다. 임의의 삼각형에 대해 세 변을 파랑, 빨강, 하양이 하나씩 나오도록 칠한다. 이제 각각의 색깔에 대해 변의 길이들을 정렬하여 파란 변의 길이를 b_1 \leq b_2 \leq \cdots \leq b_{2009}, 빨간 변의 길이를 r_1 \leq r_2 \leq \cdots \leq c_{2009}, 하얀 변의 길이를 w_1 \leq w_2 \leq \cdots \leq w_{2009}라 하자. 이 때 k개의 j가 있어 변의 길이가 b_j,r_j,w_j인 삼각형이 존재한다.

A2. 세 양의 실수 a,b,c\frac{1}{a}+\frac{1}{b}+\frac{1}{c}=a+b+c를 만족할 때 다음 부등식이 성립함을 보여라.
\displaystyle \sum_{cyc} \frac{1}{(2a+b+c)^2} \leq \frac{3}{16}

A3. 양의 정수의 집합에서 양의 정수의 집합으로 대응되는 함수 f가 임의의 x,y에 대해 x,f(y),f(y+f(x)-1)이 삼각형의 세 변의 길이가 되도록 한다. 이런 f를 모두 구하여라.

A4. ab+bc+ca \leq 3abc를 만족하는 양의 실수 a,b,c에 대해 다음 부등식이 성립함을 보여라.
\displaystyle \sum_{cyc} \sqrt{\frac{a^2+b^2}{a+b}} +3 \leq \sqrt{2}(\sum_{cyc}\sqrt{a+b})

A5. 실수의 집합에서 실수의 집합으로 대응되는 임의의 함수 f가 주어져 있다. 이 때 f(x-f(y))> yf(x)+x가 성립하는 실수 x,y가 존재함을 보여라.

A6. 강증가하는 수열 s_1,s_2,s_3,\cdots의 부분수열 s_{s_1},s_{s_2},\cdotss_{s_1+1},s_{s_2+1},\cdots가 등차수열이라 한다. 이 때 s_1,s_2,\cdots가 등차수열임을 보여라.

A7. 임의의 실수 x,y에 대해 다음 식이 성립하는 함수 f:\mathbb{R} \rightarrow \mathbb{R}을 모두 구하여라.
\displaystyle f(xf(x+y))=f(yf(x))+x^2

COMBINATORICS

C1. 2009장의 카드가 있는데, 이 카드는 한 면은 금색이고 한 면은 검은 색이다. 이들을 일렬로, 금색 면이 앞면으로 나오도록 늘어놓는다. 두 명의 사람은 다음과 같은 시행을 번갈아가며 한다. 각 사람은 맨 왼쪽 카드가 금색 카드가 되도록 연속한 50장의 카드를 선택한 후, 이 카드들을 각각 뒤집는다. 더 이상 시행이 불가능한 시점까지 이들이 시행을 했을 때 마지막으로 시행을 한 사람이 이긴다고 한다.
(a) 이 게임은 유한 시간 내에 끝나는가?
(b) 첫 번째 사람에게 필승수가 존재하는가?

C2. 임의의 정수 n \geq 2에 대해, N(n)을 다음 조건을 만족시키는 음 아닌 정수 (a_i,b_i,c_i), i=1,\cdots,N(n)이 성립하게 하는 수의 최댓값이라 하자.
(1) 임의의 i에 대해 a_i+b_i+c_i=n
(2) i \neq j이면 a_i \neq a_j, b_i \neq b_j, c_i \neq c_j
n \geq 2에 대해 N(n)을 구하여라.

C3. e_1,...,e_{n-1}을 0,1 중에서 아무렇게나 택한다. 그리고 a_0=1, a_1=7이라 하고 (1) e_i=0이면 a_{i+1}=2a_{i-1}+3a_i, (2) e_i=1이면 a_{i+1}=3a_{i-1}+a_i가 되도록 정의하고 b_0=1, b_1=7, (1) e_{n-i}=0이면 b_{i+1}=2b_{i-1}+3b_i, (2) e_{n-i}=1이면 b_{i+1}=3b_{i-1}+b_i로 정의한다. 이 때 a_n=b_n이 성립함을 보여라.
(C3는 여기에서 풀이를 다루었다.)

C4. m \geq 1인 정수에 대해, 2^m \times 2^m 모양의 체스판을 체스판의 칸들로 이루어진 직사각형들로 분할하려 한다. 이 때, 왼쪽 밑에서 오른쪽 위로 내려가는 큰 대각선 위에 놓이는 2^m개의 칸들은 각각 길이가 1인 정사각형으로 미리 분할해놓는다. 이 때 이러한 분할들의 직사각형들의 둘레의 길이의 합의 최솟값을 구하여라.

C5. 다섯 개의 비어 있는 2리터짜리 물통이 정오각형의 각 꼭지점 위에 놓여 있다. 신데렐라와 그녀의 나쁜 계모가 다음과 같은 시행을 한다. 각 턴마다, 계모는 1리터의 물을 가까운 강에서 떠와서 다섯 개의 물통들에 임의로 나누어준다. 그러면 신데렐라는 인접한 두 개의 물통을 잘 골라서 그 물통의 물들을 강물에 버리고 다시 제자리에 되돌려 놓는다. 그리고 다음 턴이 시작된다. 계모의 목표는 물통들 중 하나라도 넘치게 만드는 것이다. 신데렐라의 목표는 그것을 막는 것이다. 나쁜 계모는 목표를 달성할 수 있을까?

C6. 999 \times 999 모양의 칸에 림프룩이란 말이 다음과 같이 움직인다. 어느 칸에 있더라도 이 말은 그에 인접한 모든 칸으로 움직일 수 있다. 단, 한 번 움직일 때마다 방향을 틀어야 한다. 즉, 연속한 두 번의 움직임은 반드시 수직이어야 한다. 림프룩의 좋은 길이란 칸들로 이루어진 수열인데 모든 칸들이 서로 다르고, 림프룩이 그 순서로 위의 조건에 맞게 움직일 수 있어야 하는 것을 뜻한다. 만약 림프룩이 좋은 길로 다 지나온 후에 한 번 더 움직여서 처음 위치로 돌아올 수 있으면 이 좋은 길을 굉장한 길이라 하자. 굉장한 길 중에서 가장 긴 길은 몇 칸을 차지하는가?

C7. 임의의 정수 n \geq 2에 대해, n의 십진법 전개에 다음 시행을 거쳐 정수 h(n)을 만든다. rn의 가장 오른쪽 끝의 자리수라 하자.
(1) 만약 r=0이면, h(n)n의 십진법 전개에서 맨 오른쪽의 0을 지워서 얻는다.
(2) 만약 1 \leq r \leq 9이면, r 이상의 자리수로 이루어진 n의 오른쪽 끝 부분 중 가장 긴 부분을 R이라 하고, 그것을 제외한 왼쪽 부분을 L이라 하자. (L은 아무 글자도 없는 공집합일 수도 있다.) 그러면 h(n)은 먼저 L을 맨 앞에 쓴 후 R-1을 두 번 써서 얻는다. 예를 들면, n=17151345543일 때 L=17151, R=345543, h(n)=17151345542345542가 된다.
임의의 정수 n \geq 2에서 시작하더라도, h를 유한번 적용시켜 마지막에 1을 만들 수 있음을 보여라.

GEOMETRY

G1. 삼각형 ABCAB=AC를 만족한다. 각 A,B의 이등분선이 변 BC,ACD,E에서 만난다. 삼각형 ADC의 내심을 K라 하고 \angle{BEK}=\frac{\pi}{4}라 한다. \angle{BAC}의 값을 구하여라.

G2. 삼각형 ABC의 외심을 O라 하자. 변 CA,AB 위에 각각 P,Q를 잡는다. 변 BP,CQ,PQ의 중점을 지나는 원 k를 잡자. 만약 직선 PQ와 원 k가 접하면 OP=OQ임을 보여라.

G3. 삼각형 ABC가 있다. 내접원이 변 AB,AC와 각각 Z,Y에서 접한다. BY,CZ의 교점을 G라 하고, 사각형 BCYRBCSZ가 평행사변형이 되도록 R,S를 잡는다. GR=GS임을 보여라.

G4. 원에 내접하는 사각형 ABCD의 대각선 AC,BDE에서 만나고 직선 AD,BCF에서 만난다. AB,CD의 중점을 각각 G,H라 하자. E,G,H를 지나는 원이 직선 EF와 점 E에서 접함을 보여라.

G5. 볼록이며 어떤 점 O에 대해 대칭인 다각형 P가 있다. 이 때 P \subset R인 평행사변형 R이 있어 \displaystyle \frac{|R|}{|P|} \leq \sqrt{2}이 되도록 할 수 있음을 보여라. 여기서 |R|,|P|는 각각 R,P의 넓이이다.

G6. 사각형 ABCD의 변 AB,CD는 평행이 아니고, AD,BC가 점 P에서 만난다. 삼각형 ABP,DCP의 외심을 각각 O_1,O_2, 수심을 각각 H_1,H_2라 하자. O_1H_1,O_2H_2의 중점을 각각 E_1,E_2라 하자. 이 때 E_1에서 CD에 내린 수선과 E_2에서 AB에 내린 수선과 H_1H_2는 한 점에서 만남을 보여라.

G7. 삼각형 ABC의 내심을 I라 하고 BIC,CIA,AIB의 내심을 각각 X,Y,Z라 하자. 삼각형 XYZ가 정삼각형이면 삼각형 ABC도 정삼각형임을 보여라.

G8. 원에 외접하는 사각형 ABCD에서 A를 지나는 직선 g가 변 BCM에서 만나고 직선 CDN에서 만난다. \triangle{ABM},\triangle{MNC},\triangle{NDA}의 내심을 각각 I_1,I_2,I_3이라 하자. 삼각형 I_1I_2I_3의 수심이 g 위에 옴을 보여라.

NUMBER THEORY

N1. 사교회에 n명이 있다. 이들은 번호 1,2,\cdots,n이 주어져 있다. 회원들은 다른 회원들에게 선물을 보내는데, 이 선물에는 그 회원이 이미 다른 회원에게서 받은 것도 포함된다. 어떤 회원이 보낸 선물을 다시 받게 되는 당혹스러운 불상사를 막기 위해, 사교회에서는 연차회의에서 다음과 같은 규칙을 발표했다.
a라는 번호를 가진 회원은 a(b-1)n의 배수여야만 b에게 선물을 보낼 수 있다.”
만약 모든 회원이 이 규칙을 따른다면, 위에서 설명한 불상사가 일어나지 않음을 보여라.

N2. 만약 N=1이거나 N이 서로 다를 필요는 없는 짝수 개의 소수의 곱으로 표현된다면 N을 균형잡힌 수라 하자. 주어진 양의 정수 a,b에 대해 다항식 PP(x)=(x+a)(x+b)로 정의하자.
(a) P(1),P(2),\cdots,P(50)이 전부 균형잡힌 수가 되는 서로 다른 양의 정수 a,b가 존재함을 보여라.
(b) 만약 모든 양의 정수 n에 대해 P(n)이 균형잡힌 수가 된다면 a=b임을 보여라.

N3. 상수함수가 아닌 함수 f:\mathbb{N} \rightarrow \mathbb{N}가 있어 임의의 서로 다른 a,b에 대해 a-bf(a)-f(B)을 나눈다고 한다. 이 때 무수히 많은 소수 p가 존재하여 어떤 c에 대해 pf(c)를 나눔을 보여라.

N4. 임의의 2 \leq k \leq n-1k에 대해 a_{k+1}=\frac{a_k^2+1}{a_{k-1}+1}-1을 만족시키는 양의 정수 수열 a_1,a_2,\cdots,a_n이 존재하는 양의 정수 n을 모두 구하여라.

N5. P(x)는 정수계수 다항식으로 상수함수가 아니다. 이 때 임의의 n \geq 1에 대해 T^n(x)=x를 만족하는 정수 x의 개수가 P(n)이 되는 함수 T:\mathbb{Z} \rightarrow \mathbb{Z}가 존재하지 않음을 보여라. 단 T^n이란 Tn번 합성한 함수이다.

N6. k는 양의 정수이다. 만약 임의의 n \geq 1에 대해 a_n=\frac{a_{n-1}+n^k}{n}가 성립하는 정수 수열 a_0,a_1,\cdots가 성립하면 k-2가 3의 배수임을 보여라.

N7. a,b는 1보다 큰 서로 다른 정수이다. 이 때 (a^n-1)(b^n-1)이 완전제곱수가 아닌 양의 정수 n이 존재함을 보여라.

한 조합등식과 그 별해들

jackal_anu님의 블로그에서 퍼온 문제와 그 원형이 되는 문제 (sos440님의 블로그에서 퍼옴).

먼저 sos440님 블로그에 올라온 문제는 다음과 같다.

n이 음 아닌 정수이면 \displaystyle \sum_{k=0}^n \binom{n+k}{n}\frac{1}{2^{n+k}}=1이 성립한다.

이 문제도 여러 가지의 풀이를 발견하였다. 사실 예전에 봤던 문제인데 어디에서 봤는지는 기억이 잘 안 난다.

First Solution. 문제를 조금 바꾸어 \displaystyle \sum_{k=0}^n \frac{1}{2^k}\binom{n+k}{n}=2^n임을 증명하자. 이것의 생성함수는 \displaystyle \sum_{n=0}^{\infty}\sum_{k=0}^n\binom{n+k}{n}2^{-k}x^n=\sum_{k=0}^{\infty}\sum_{n=k}^{\infty}\binom{n+k}{n}2^{-k}x^n, 즉 \displaystyle \sum_{k=0}^{\infty}2^{-k} \left(\binom{2k}{k}x^k+\binom{2k+1}{k}x^{k+1}+\cdots \right)가 된다.

여기서 잠시 다른 길로 빠진다. 다음 Lemma를 보자.
Lemma. \displaystyle P_c(x)=\sum_{n=0}^{\infty}\binom{2n+c}{n}x^n이라 하자. 그러면 \displaystyle P_c(x)=\frac{1}{\sqrt{1-4x}} \left( \frac{1-\sqrt{1-4x}}{2x} \right)^n가 성립한다.
Proof of Lemma. P_c(x)=xP_{c+1}(x)+P_{c-1}(x)임을 쉽게 얻을 수 있다. (주세걸의 항등식 혹은 반데르몬드의 항등식) P_0(x)=\frac{1}{\sqrt{1-4x}}임과 P_1(x)=\sum \binom{2n+1}{n}x^n = \sum \frac{1}{2} \binom{2n+2}{n+1}x^n = \frac{P_0-1}{2x}임에서 점화식을 풀면 원하는 결과를 얻는다. QED

따라서 다시 원래 식으로 돌아가면 그 식은 \displaystyle \sum_{k=0}^{\infty} \left( \binom{2k}{k}( \frac{x}{2})^k + \binom{2k+1}{k} (\frac{x}{2})^k x + \cdots \right)
\displaystyle =\frac{1}{\sqrt{1-2x}} \left( 1+(1-\sqrt{1-2x})+(1-\sqrt{1-2x})^2+\cdots \right)
\displaystyle =\frac{1}{\sqrt{1-2x}} \frac{1}{1-(1-\sqrt{1-2x})}
\displaystyle =\frac{1}{\sqrt{1-2x}} \frac{1}{\sqrt{1-2x}} = \frac{1}{1-2x}가 된다. 따라서 그 x^n의 계수는 2^n이 되므로 증명이 끝난다.

다음은 조합적인 풀이. 아쉽게도 내가 발견한 것은 아니고, 이 문제가 올라왔을 때 같이 있었던 풀이이다. 누구 것인지마저 가물..

Second Solution. 문제를 바꾸어 \displaystyle \sum_{k=0}^n \binom{n+k}{n}2^{n+1-k}=2^{2n+1}임을 증명한다. O와 X를 적당히 택해 길이 2n+1인 것들을 본다. 전체 개수는 2^{2n+1}이다. 이제 O와 X가 홀수개이므로 어느 하나는 반드시 다른 하나보다 개수가 커야 한다. 이제 O가 X보다 많은 경우를 보자. 이 경우 O의 개수는 n+1개 이상이어야 한다. 이 때 n+1번째 O의 위치를 선택한 후 개수를 세어보자. 그 O는 n+1,n+2,\cdots,2n+1번째 위치에 올 수 있다. 이것이 오는 위치를 n+1+k번째 위치라 하자. 그러면 그 앞에는 O가 n개, X가 k개 있어야 하므로 그 개수는 \binom{n+k}{n}이다. 그리고 n+1번째 O의 오른쪽에는 O,X가 아무렇게나 배열될 수 있으므로 그 개수는 2^{n-k}이다. 따라서 이러한 가지수는 \displaystyle \sum_{k=0}^n \binom{n+k}{n}2^{n-k}이다. X가 O보다 많은 경우도 마찬가지로 같은 값이므로, 이 식에 2를 곱한 값인 좌변은 2^{2n+1}이 되어 증명이 끝난다.

다음은 아마 수학 올림피아드를 공부하는 학생들 중 대다수가 발견할 법한 수학적 귀납법 풀이.

Third Solution n=0인 경우는… 자명하다. n인 경우 성립을 가정하고 n+1인 경우를 본다. 그러면 \displaystyle \binom{2n+1}{n+1}\frac{1}{2^{2n+1}}+\binom{2n+2}{n+1}\frac{1}{2^{2n+2}} = \binom{2n+1}{n+1}\frac{1}{2^{2n+1}}+\binom{2n+1}{n}\frac{1}{2^{2n+1}}=\binom{2n+1}{n+1}\frac{1}{2^{2n}}이므로 n+1일 때의 식에서 n일 때의 식을 빼주면
\displaystyle \binom{n+1}{n+1}\frac{1}{2^{n+1}}+\cdots+\binom{2n}{n+1}\frac{1}{2^{2n}}+\binom{2n+1}{n+1}\frac{1}{2^{2n+1}}+\binom{2n+2}{n+1}\frac{1}{2^{2n+2}}-\binom{n}{n}\frac{1}{2^n}-\cdots-\binom{2n}{n}\frac{1}{2^{2n}}
\displaystyle =\binom{n+1}{n+1}\frac{1}{2^{n+1}}+\cdots+\binom{2n}{n+1}\frac{1}{2^{2n}}+\binom{2n+1}{n+1}\frac{1}{2^{2n}}-\binom{n}{n}\frac{1}{2^n}-\cdots-\binom{2n}{n}\frac{1}{2^{2n}}
\displaystyle =\binom{n+1}{n+1}\frac{1}{2^{n+1}}+\cdots+\binom{2n}{n+1}\frac{1}{2^{2n}}+\binom{2n}{n+1}\frac{1}{2^{2n}}-\binom{n}{n}\frac{1}{2^n}-\cdots-\binom{2n-1}{n}\frac{1}{2^{2n-1}}
\displaystyle = \binom{n+1}{n+1}\frac{1}{2^{n+1}}+\cdots+\binom{2n-1}{n+1}\frac{1}{2^{2n-1}}+\binom{2n}{n+1}\frac{1}{2^{2n-1}}-\binom{n}{n}\frac{1}{2^n}-\cdots-\binom{2n-1}{n}\frac{1}{2^{2n-1}}
이 된다. 여기서 잘 보면, 두 번째 식의 2n2n-1로 바꾼 식이 네 번째 식이다. 즉 위의 과정은 항을 두 개씩 줄이는 과정이 되고 이를 계속 하면 그 결과는 \displaystyle \binom{n+1}{n+1}\frac{1}{2^{n+1}}+\binom{n+2}{n+1}\frac{1}{2^{n+1}}-\binom{n}{n}\frac{1}{2^n}-\binom{n+1}{n}\frac{1}{2^{n+1}}이 되고 이것이 0임은… 또 자명하다. 끝.

위의 증명에서 중간에 얻은 사실을 (수학적 귀납법의 step) 정리하면 다음과 같이 쓸 수 있다.
Lemma. \displaystyle \sum_{k=n+1}^m \binom{k}{n+1}\frac{1}{2^k}+\binom{m+1}{n+1}\frac{1}{2^m} = \sum_{k=n}^{m} \binom{k}{n}\frac{1}{2^k}

이제 다음 풀이를 보자. 이번엔 생성함수를 다른 방법으로 응용하였다. 후에 보게 되겠지만, 이 방법은 일반화에서도 유효하다.

Fourth Solution. \displaystyle \sum_{k=0}^n 2^{n-k}\binom{n+k}{n}=2^{2n}임을 보이자. 좌변은 \displaystyle \frac{1}{1-2x} \frac{1}{(1-x)^{n+1}}x^n의 계수가 됨을 알 수 있다. 그런데 \displaystyle \frac{1}{1-2x} \frac{1}{(1-x)^{n+1}}을 partial fractions로 나타내면 그 결과는 \displaystyle \frac{2^{n+1}}{1-2x}-\frac{2^n}{1-x}-\frac{2^{n-1}}{(1-x)^2}-\cdots-\frac{2^0}{(1-x)^{n+1}}이다. 따라서 이 식의 x^n의 계수는 \displaystyle 2^{n+1}2^n - 2^n \binom{n}{n}-2^{n-1}\binom{n+1}{n}-\cdots-2^0\binom{2n}{n}이 되는데, 잘 보면, \displaystyle 2^n \binom{n}{n}+2^{n-1}\binom{n+1}{n}+\cdots+2^0\binom{2n}{n}이 바로 우리가 구하는 값이다. (!) 따라서 이 값을 S라 하면 S=2^{2n+1}-S가 되어 S=2^{2n}이 되어 증명이 끝난다.

이제 이것의 일반화인 jackal_anu 님의 조합등식을 보자.

p,q가 음 아닌 정수이면 \displaystyle \sum_{k=0}^q \frac{1}{2^{p+k}}\binom{p+k}{k}+\sum_{k=0}^p \frac{1}{2^{q+k}}\binom{q+k}{k}=2가 성립한다.

p=q를 대입하면 처음에 소개한 조합등식을 얻을 수 있다.

First Solution. 위 문제의 Third Solution에서 쓴 방법을 그대로 이용한다. p는 그대로 놔두고 q에 대한 수학적 귀납법을 쓴다. q=0이면 \displaystyle \frac{1}{2^p}\binom{p}{0}+\binom{0}{0}+\frac{1}{2}\binom{1}{1}+\cdots+\frac{1}{2^p}\binom{p}{p}=2를 얻는다. 이제 q일 때 성립함을 가정하고 q+1일 때의 식에서 q일 때의 식을 빼면 그 값은
\displaystyle \frac{1}{2^{p+q+1}}\binom{p+q+1}{q+1} + \sum_{k=q+1}^{p+q+1}\frac{1}{2^k}\binom{k}{k-q-1} - \sum_{k=q}^{p+q} \frac{1}{2^k} \binom{k}{k-q}인데 이 식 정리하면 위의 Lemma에서 n=q,m=p+q를 대입한 것이 되어 0이다. 끝. (원래 문제의 Third Solution의 analogue)

Second Solution. 문제를 바꿔 \displaystyle 2^{p+q+1}=\sum_{k=0}^q 2^{q-k}\binom{p+k}{p} + \sum_{k=0}^p 2^{p-k}\binom{q+k}{q}임을 보이자. 앞 문제의 Fourth Solution과 비슷하게 생각하면, 앞의 summation은 \displaystyle [x^q]\frac{1}{1-2x}\frac{1}{(1-x)^{p+1}}이고 뒤의 summation은 \displaystyle [x^p]\frac{1}{1-2x}\frac{1}{(1-x)^{q+1}}이다. 앞에서 구한 결과를 이용하면 앞의 summation은 \displaystyle [x^q]( \frac{2^{p+1}}{1-2x}-\frac{2^p}{1-x}-\cdots-\frac{2^0}{(1-x)^{p+1}}이므로 \displaystyle 2^{p+q+1}-2^p\binom{q}{q}-2^{p-1}\binom{q+1}{q}-\cdots-2^0\binom{q+p}{q}가 된다. 마찬가지로 두 번째 summation의 값은 \displaystyle 2^{q+p+1}-2^q\binom{p}{p}-2^{q-1}\binom{p+1}{p}-\cdots-2^0\binom{p+q}{p}이다. 그런데 이번에도, 두 summation의 결과의 첫항을 제외한 것들은 원래 값과 같다! 그래서 그 합을 S라 하면 S=2^{p+q+2}-S가 되어 원하는 결과를 얻는다. (원래 문제의 Fourth Solution의 analogue)

Third Solution. 역시 \displaystyle 2^{p+q+1}=\sum_{k=0}^q 2^{q-k}\binom{p+k}{p} + \sum_{k=0}^p 2^{p-k}\binom{q+k}{q}를 보이자. 이번엔 앞의 문제의 Second Solution을 응용하자. O과 X를 p+q+1개를 늘어놓는다. 그러면 O가 p+1개 이상 나오거나 X가 q+1개 나오거나 둘 중 하나이며, 두 event가 동시에 일어날 수 없다. 앞의 경우 p+1번째 O가 나오는 곳이 p+k+1이라 하면 그 가지수는 \binom{p+k}{p}2^{q-k}가 된다. 이들을 모든 k에 대해 더하면 첫 번째 summation. 마찬가지로, 두 번째 event의 경우의 수가 두 번째 summation이 되어 증명이 끝난다.

여기서 부가적으로 \displaystyle \sum_{k=0}^q 2^{q-k}\binom{p+k}{p} = \sum_{k=0}^q \binom{p+q+1}{k}가 됨을 확인할 수 있다. 이는 앞의 문제의 refinement가 되겠다.

A Weak Generalization. \displaystyle \sum_{k=0}^q 2^{q-k}\binom{p+k}{p} = \sum_{k=0}^q \binom{p+q+1}{k}

jackal_anu 님의 마지막 일반화를 보자. 다음 등식 역시 sos440님의 등식이다.

p,q가 음 아닌 정수이면 \displaystyle (1-x)^{p+1}\sum_{k=0}^q\binom{p+k}{p}x^k+x^{q+1}\sum_{k=0}^p\binom{q+k}{q}(1-x)^k=1이 성립한다.

x=\frac{1}{2}를 대입하면 위의 문제가 됨을 확인할 수 있다.

First Solution. jackal_anu 님의 풀이. 이 풀이는 앞의 문제의 Third Solution과 관련이 깊다. 간략히 설명하자면, O,X를 p+q+1개 쓰되 O가 나올 확률을 1-x, X가 나올 확률을 x로 두고 O가 p+1개 이상 나오는 확률과 X가 q+1개 이상 나오는 확률의 합이 1임을 이용한다.

Second Solution. sos440님의 풀이. 또 간략히 설명하자면
\displaystyle \sum_{k=1}^{q} \binom{p+1+k}{k} x^k=\sum_{k=1}^{q} \sum_{j=0}^{k} \binom{p+j}{j} x^k
\displaystyle =\sum_{j=0}^{q} \sum_{k=j}^{q} \binom{p+j}{j} x^k=\sum_{j=0}^{q} \binom{p+j}{j} \frac{x^j - x^{q+1}}{1-x}
\displaystyle =\sum_{k=0}^{q} \binom{p+k}{k} \frac{x^k-x^{q+1}}{1-x}=\frac{1}{1-x} \left( \sum_{k=0}^{q} \binom{p+k}{k} x^k - \binom{p+q+1}{q} x^{q+1} \right)
임을 이용한다.

It’s my turn!

Third Solution. 설마 수학적 귀납법이 또 통할줄이야… 원래 문제의 Third Solution, 두 번째 문제의 First Solution의 뜻을 계승한다. 대략적인 설명만 하자면 q에 대한 수학적 귀납법으로 q=0인 경우는 또 자명하고 q+1일 때의 식에서 q일 때의 식을 빼면 그 결과가 정리하면 \displaystyle \sum_{k=0}^{p-1}\binom{q+1+k}{q+1}x(1-x)^{k}+\binom{q+p+1}{q+1}(1-x)^p - \sum_{k=0}^{p}\binom{q+k}{q}(1-x)^k가 되는데, 이번에도 맨 끝에서 장난을 쳐서 두 항을 없애는 식으로 계속 해나가면 0이 되어 원하는 결과를 얻는다.

Fourth Solution. 설마 생성함수 방법도 또 통할줄이야…… 원래 문제의 Fourth Solution, 두 번째 문제의 Second Solution과 뜻을 같이한다. 식을 변형하여 \displaystyle (1-x)\sum_{k=0}^q\binom{p+k}{p}\frac{1}{x^{q-k}}+x\sum_{k=0}^p\binom{q+k}{q}\frac{1}{(1-x)^{p-k}}=\frac{1}{x^q(1-x)^p}임을 보인다. 첫 번째 summation을 보자. 이것은 앞에서와 마찬가지로 생각하면 \displaystyle [z^q](1-x)\frac{1}{1-\frac{z}{x}}\frac{1}{(1-z)^{p+1}}인데, \displaystyle (1-x)\frac{1}{1-\frac{z}{x}}\frac{1}{(1-z)^{p+1}}을 partial fractions로 표현하면 그 결과 \displaystyle \frac{1}{(1-x)^p}\frac{1}{1-\frac{z}{x}}-\frac{x}{(1-x)^p}\frac{1}{1-z}-\cdots-\frac{x}{(1-x)^0}\frac{1}{(1-z)^{p+1}}이 된다. 이것의 z^q의 계수는 \frac{1}{(1-x)^p}\frac{1}{x^q}-\frac{x}{(1-x)^p}\binom{q}{q}-\cdots-\frac{x}{(1-x)^0}\binom{q+p}{q}가 되는데, 여기서 첫 항을 제외한 뒤의 항들의 합은 원래 식에서의 두 번째 summation이 되어 바로 증명이 끝난다. (합해서 2 \frac{1}{(1-x)^p}\frac{1}{x^q}-S=S이므로 어쩌구 이런 식의 논의로 해도 상관은 없다.)

Fifth Solution. 먼저 위 문제의 Third Solution에서 refine하듯 여기서도 First Solution에 의거하여 refine할 수 있다. 그 식이란 \displaystyle (1-x)^{p+1}\sum_{k=0}^q \binom{p+k}{k}x^k= \sum_{k=0}^q \binom{p+q+1}{k}x^k(1-x)^{q-k}이다. 여기서 1-x=y라 하고 x+y=1임을 이용하여 homogenization하면 다음과 같은 이쁜 식을 얻는다.
A Bit Stronger Generalization. \displaystyle \sum_{k=0}^q\binom{p+k}{k}x^k(x+y)^{q-k}=\sum_{k=0}^q\binom{p+q+1}{k}x^ky^{q-k}
이 일반화는 앞에서의 A Weak Generalization의 일반화도 된다. x=y=1을 대입하면..
이제 이 일반화를 증명하자. 0 \leq n \leq q에 대해 x^ny^{q-n}의 계수를 비교하면, \displaystyle \binom{p}{0}\binom{q}{n}+\binom{p+1}{1}\binom{q-1}{n-1}+\cdots+\binom{p+n}{n}\binom{q-n}{0}=\binom{p+q+1}{n}임을 보이면 된다. (거의 다른 문제로 바뀌었다!) 이 식의 좌변은 \displaystyle \left( \binom{p}{0}+\binom{p+1}{1}x+\cdots \right) \left( \binom{q-n}{0}+\binom{q-n+1}{1}x+\cdots \right), 즉 \displaystyle \frac{1}{(1-x)^{p+q-n+2}}x^n의 계수이다. 따라서 그 값은 \displaystyle \binom{(p+q-n+1)+n}{p+q-n+1}=\binom{p+q+1}{n}이 되어 증명이 끝난다.

Sixth Solution. 이 풀이로 별해 개수를 늘리는게 큰 의미가 있을까도 싶다만.. 앞의 A Bit Stronger Generalization을 다른 방법으로 증명한다. 먼저 위 식에 q 대신 q+n을 대입해 대칭꼴인 \displaystyle \sum_{k=0}^n \binom{p+k}{p}\binom{q+n-k}{q}=\binom{p+q+n+1}{n}으로 바꾼다. 이제 1,2,\cdots,p+q+n+1에서 p+q+1개의 수를 택하는 경우를 보자. 그 경우의 수는 물론 \binom{p+q+n+1}{p+q+1}, 즉 우변이다. 한 편 크기순으로 p+1번째 수가 무엇인지를 주목하자. 그것은 p+1,p+2,\cdots,p+n+1가 후보인데 p+1+k라 하면 그보다 작은 수들에선 p개를 뽑아야 해 경우의 수가 \binom{p+k}{p}가 되고 그보다 큰 수들에선 q개를 뽑아야 해 경우의 수가 \binom{q+k}{q}가 된다. 따라서 이들을 곱해 전부 합하면 그 값은 좌변이 되어 문제가 증명된다.

Any other solutions?