2010 JMO 예선 #9

2010년에 있었던 일본 수학 올림피아드의 예선 9번 문제. 일본에서는 예선으로 12문제가 나오는데 예전에 일본 학생에게서 들은 기억에는 이 문제를 다 풀어야 하는 것이 아니라 몇 문제를 골라서 푸는 것으로 기억한다. (그런데 그게 몇 문제인지는 또 기억이 안 난다..) 아무튼 문제는 다음과 같다.

흰 돌 2010개와 검은 돌 2010개를 가로 일렬로 늘어놓을 때, 다음 조건을 만족하는 가지수는 몇 가지인가?
– 흰 돌 하나와 검은 돌 하나를 택했을 때 흰 돌이 검은 돌보다 오른쪽에 오는 경우가 홀수 개다.

즉 흰 돌을 X, 검은 돌을 O이라 하면 O하나를 택하고 그 오른쪽에 있는 X를 또 택하는 경우의 수가 총 홀수 개가 되는 나열법이 몇 가지인가를 묻는 것이다. 예컨대 XOOXOX라면 첫 O는 오른쪽의 X가 2개, 두 번째 O는 오른쪽의 X가 2개, 세 번째 O는 오른쪽의 X가 1개므로 총 5개로 홀수 개이다. 이런 것이 몇 개 있는지를 묻는 문제이다.

이 문제를 조금 더 일반화하여, 다음과 같이 다시 쓰자.

흰 돌 n개와 검은 돌 n개를 가로 일렬로 늘어놓되, 흰 돌 하나와 검은 돌 하나를 택했을 때 흰 돌이 검은 돌보다 오른쪽에 오는 경우가 홀수 개가 되도록 하고 싶다.
(1) n이 홀수일 때 그 경우의 수를 구하여라.
(2) n이 짝수일 때 그 경우의 수를 구하여라.

n이 작은 경우 몇 가지를 보다 보면, (1)의 답은 쉽게 추측이 가능하다. (1)의 답은 \frac{1}{2}\binom{2n}{n}이다. 한 편 (2)의 답은 바로 추측이 되지 않는데, 그 답은 \frac{1}{2}(\binom{2n}{n}-\binom{n}{n/2})이다. 이를 몇 가지 방법으로 증명하자.

First Solution 먼저 (1)의 간단한 풀이를 보자. 앞에서처럼 O이 X의 왼쪽에 있는 것이 홀수 개인 경우를 세자. O n개와 X n개를 나열한 것 중 하나를 a라 하고, 그를 거꾸로 나열한 것을 b라 하자. 그러면 a에서 (O,X)의 개수는 b에서 (X,O)의 개수와 같고, 즉 a,b에서의 (O,X)의 개수의 합은 a에서의 (O,X)와 (X,O)의 개수를 세는 것이 된다. 이는 O 중 하나, X 중 하나를 택하기만 하면 되므로 총 n^2개로 홀수이다. 따라서 a에서 (O,X)의 개수가 홀수였다면 b는 짝수이고, a가 짝수였다면 b는 홀수이다. 따라서 이것은 짝수인 것과 홀수인 것의 일대일 대응이 되고 그 개수는 정확히 같아야 한다. (뒤집어서 같게 나오는 것은 없음을 유의하자.) 따라서 그 개수는 전체 \binom{2n}{n}개의 절반인 \frac{1}{2}\binom{2n}{n}이다.

이 풀이는 (2)에선 적용되지 않는다. 왜냐하면 n^2가 짝수이기 때문에, 짝수인 것과 홀수인 것의 일대일 대응인 것을 보일 수가 없기 때문이다.

Second Solution 이제 보일 풀이는 (1)도 (2)도 적용되는 풀이이다. 먼저 (2)의 경우를 본다. (O,X)의 개수가 홀수인 것의 집합을 A라 하고, 짝수인 것의 집합을 B라 하자. 이 때 다음과 같은 대응 f:A \cup B \rightarrow A \cup B을 생각하자. 먼저, A의 임의의 원소 a를 두 자리씩 나눈다. 예를 들어 OO|XX|XX|OX|OO|XO 이런 식으로 두 자리씩 나눈다. 그러면 만약 OX나 XO가 나오지 않으면 f(a)=a로 정의하고, OX나 XO가 하나 이상 나오면 최초로 나오는 OX나 XO를 각각 XO와 OX로 바꾼 것을 f(a)로 정의한다. 그러면 이 경우는 (O,X)의 쌍의 개수가 정확히 하나 바뀌기 때문에 f(a)B에 속한다. 마찬가지로 B의 원소에 대해서도 똑같이 정의한다. 그러면 AB의 원소들 중에서 OX나 XO가 나오지 않는 것들을 제외하곤 AB가 일대일 대응이 된다.
그런데 OX와 XO가 없다는 것은 곧 두 자리로 나눈 결과가 OO과 XX만 나오는 것인데, 이 때 (O,X)의 개수는 반드시 짝수개다. 곧 그런 것들은 전부 B의 원소이다. 이런 것들의 개수는 OO \frac{n}{2}개와 XX \frac{n}{2}개를 배열하는 가지수이므로 \binom{n}{n/2}이다. 즉, A의 원소와 B의 원소 중 \binom{n}{n/2}개를 제외한 것들이 일대일 대응이 되므로 A의 원소의 개수(우리가 구하고자 하는 값)를 x라 하면 |A|=x, |B|=x+\binom{n}{n/2}이다. \binom{2n}{n}=|A|+|B|=2x+\binom{n}{n/2}이므로, 답은 \frac{1}{2}(\binom{2n}{n}-\binom{n}{n/2})이다.

마찬가지 풀이를 n이 홀수일 때에도 적용할 수 있다. 이 경우 OX와 XO가 없는 경우가 없다. 즉 O가 홀수 개, X가 짝수 개 있으므로 반드시 두 개씩 나눌 때 OX나 XO가 등장한다. 따라서 완벽히 AB가 일대일 대응이 되고 그 개수는 전체의 절반이 되어 같은 답이 나온다.

Third Solution 이번엔 생성함수를 이용한 풀이를 보자. 먼저 O m개, X n개인 경우 O이 X의 왼쪽에 있는 것이 홀수 개인 경우의 수를 f(m,n)이라 하자. 이제 f(2n,2n)=\frac{1}{2}(\binom{4n}{2n}-\binom{2n}{n})임을 보이자.

먼저 f(m,n)의 점화식을 찾아내자. 맨 앞의 것이 O인지 X인지를 따짐으로써, n이 짝수이면 f(m,n)=f(m-1,n)+f(m,n-1)이고 n이 홀수이면 f(m,n)=\binom{m+n-1}{m-1}-f(m-1,n)+f(m,n-1)가 됨을 확인할 수 있다. 이를 이용해 생성함수를 만들어낸다. f(0,n)=f(m,0)=0임을 주의하자.

이 점화식을 이용하여 f(2a,2b)=\binom{2a+2b-2}{2a-1}+f(2a-2,2b)+f(2a,2b-2)임을 얻을 수 있다. 따라서 \displaystyle F(x,y)=\sum_{a,b\geq 0}f(2a,2b)x^ay^b라고 두면 이 점화식으로부터 \displaystyle F(x,y)=\sum \binom{2a+2b-2}{2a-1}x^ay^b + (x+y)F(x,y), 즉 \displaystyle F(x,y)=\frac{1}{1-x-y}\sum \binom{2a+2b-2}{2a-1}x^ay^b가 된다.

이제 \sum \binom{2a+2b-2}{2a-1}x^ay^b를 구하자. 이는 \displaystyle \sum_{a \geq 1}x^a\sum_{b \geq 1}\binom{2a+2b-2}{2a-1}y^b이 되는데 \displaystyle \sum_{b \geq 1}\binom{2a+2b-2}{2a-1}y^b = \binom{2a}{2a-1}y+\binom{2a+2}{2a-1}y^2+\cdots의 값은 \displaystyle \frac{1}{2} \left( \frac{1}{(1-y)^{2a}}-\frac{1}{(1+y)^{2a}} \right)=\binom{2a}{2a-1}y+\binom{2a+2}{2a-1}y^3+\cdots에서 양변에 y를 곱하고 y\sqrt{y}를 대입하여 얻을 수 있다. 그 결과 \displaystyle \sum \binom{2a+2b-2}{2a-1}x^ay^b = \sum_{a \geq 1} x^a \frac{\sqrt{y}}{2} \left( \frac{1}{(1-\sqrt{y})^{2a}}-\frac{1}{(1+\sqrt{y})^{2a}} \right)이므로 \displaystyle \sum \binom{2a+2b-2}{2a-1}x^ay^b = \frac{\sqrt{y}}{2} \left( \frac{x}{(1-\sqrt{y})^2}\frac{1}{1-\frac{x}{(1-\sqrt{y})^2}} \right) - \frac{\sqrt{y}}{2} \left( \frac{x}{(1+\sqrt{y})^2}\frac{1}{1-\frac{x}{(1+\sqrt{y})^2}} \right)이다. 이를 정리하면 \displaystyle \frac{2xy}{1+x^2+y^2-2x-2y-2xy}가 된다. 따라서 \displaystyle F(x,y)=\frac{2xy}{(1-x-y)(1+x^2+y^2-2x-2y-2xy)}을 얻는다.

이제 여기서부터 G(t)=f(0,0)+f(2,2)t+f(4,4)t^2+\cdots를 얻고자 한다. 이를 위해 (x,y)(xy,\frac{x}{y})를 대입한 후에 y^0의 계수를 보면 그 결과가 G(x^2)가 되므로 x=\sqrt{t}를 대입하면 된다.

(xy,\frac{x}{y})를 대입하면 그 결과 \displaystyle F(xy,\frac{x}{y})=\frac{2x^2}{(1-x(y+\frac{1}{y}))(1+x^2(y^2+\frac{1}{y^2})-2x(y+\frac{1}{y})-2x^2)}인데 여기서 z=y+\frac{1}{y}를 대입하면 이는 \displaystyle \frac{2x^2}{(1-xz)(1-4x^2-2xz+x^2z^2)}=\frac{2x^2}{(1-xz)(1+2x-xz)(1-2x-xz)}이고, 이를 부분분수로 나누면 그 결과는 \displaystyle -\frac{1}{2}\frac{1}{1-xz}+\frac{1}{4}\frac{1}{1+2x}\frac{1}{1-\frac{x}{1+2x}z}+\frac{1}{4}\frac{1}{1-2x}\frac{1}{1-\frac{x}{1-2x}z}, 즉 \displaystyle -\frac{1}{2}(1+x(y+\frac{1}{y}+\cdots)+\frac{1}{4}\frac{1}{1+2x}(1+\frac{x}{1+2x}(y+\frac{1}{y})+\cdots)+\frac{1}{4}\frac{1}{1-2x}(1+\frac{x}{1-2x}(y+\frac{1}{y})+\cdots)이다. 여기서 y^0의 계수는 \displaystyle -\frac{1}{2}(1+\binom{2}{1}x^2+\binom{4}{2}x^4+\cdots)+\frac{1}{4}\frac{1}{1+2x}(1+\binom{2}{1}(\frac{x}{1+2x})^2+\cdots)+\frac{1}{4}\frac{1}{1-2x}(1+\binom{2}{1}(\frac{x}{1-2x})^2+\cdots)이 된다. 맨 앞 항을 제외한 나머지 두 항은 \displaystyle 1+\binom{2}{1}x+\binom{4}{2}x^2+\cdots=\frac{1}{\sqrt{1-4x}}임을 이용하면 \displaystyle \frac{1}{4}\frac{1}{1+2x}\frac{1}{\sqrt{1-\frac{4x^2}{(1+2x)^2}}}+\frac{1}{4}\frac{1}{1-2x}\frac{1}{\sqrt{1-\frac{4x^2}{(1-2x)^2}}}이 되고 정리하면 \displaystyle \frac{1}{4}\frac{1}{\sqrt{1+4x}}+\frac{1}{4}\frac{1}{\sqrt{1-4x}}=\frac{1}{2}(1+\binom{4}{2}x^2+\binom{8}{4}x^4+\cdots)가 된다. 따라서 G(x^2)x^{2n}의 계수는 \displaystyle \frac{1}{2}\binom{4n}{2n}-\frac{1}{2}\binom{2n}{n}이 되고 이것이 곧 f(2n,2n)이므로 증명이 끝난다.

(1) 역시 마찬가지 방법으로 증명이 되지만, 풀이가 비슷하게 길어서 생략.

내가 이 문제를 풀면서 시도한 방법은.. 먼저 답을 추측하는 것. 그리고 그것을 증명할 때 먼저 일대일 대응을 찾는 것이다. 그를 찾는 과정에서 먼저 First Solution의 방법을 찾아냈으나 그것은 짝수인 경우를 증명할 수 없었다. 그래서 조금 더 시도한 결과 Second Solution을 찾아냈다. 여기서 멈추지 않고 점화식을 찾아내어 생성함수 풀이를 찾아냈다.

다른 풀이는 무엇이 있을까?

Advertisements
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: