2009 IMO Short-list C3

이번 IMO 쇼트리스트 문제 중에서 가장 흥미로웠던 문제.

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이 성립함을 보여라.

즉 초기값은 1,7로 고정되어 있는데, 이진 수열이 주어져 있고 그것에 따라 점화식을 바꾸면 이진 수열을 거꾸로 주더라도 결과가 같게 나온다는 것이다. 밑의 풀이를 보면 알겠지만 일반적인 경우 다 되는 것은 아니고, 1과 7, 2와 3, 3과 1이 적당히 잘 주어져서 나온 결과이다. 러시아에서 제출한 문제.

이하는 official solution.

w=\sigma_1 \cdots \sigma_n이란 이진수열이 주어져 있을 때 이것을 거꾸로 한 것을 \bar{w}=\sigma_n \cdots \sigma_1이라 한다. 또한 \emptyset을 아무 글자도 없는 이진수열이라 하자. 이제 a_n=(u,v)^w,b_n=(u,v)^{\bar{w}}꼴이 되도록 다음과 같이 (u,v)^w를 잘 정의한다.

(u,v)^{\emptyset}=v, (u,v)^0=2u+3v,(u,v)^1=3u+v
(u,v)^{w\sigma \epsilon}=2(u,v)^w+3(u,v)^{w\sigma} (\sigma는 0 또는 1이며 \epsilon=0)
(u,v)^{w\sigma \epsilon}=3(u,v)^w+(u,v)^{w\sigma} (\sigma는 0 또는 1이며 \epsilon=1)
(정의에 매달리지 말고, 이것이 수열의 정의와 어떤 연관성이 있고 왜 이렇게 정의했는지의 필연성을 느껴보길 바란다.)

이 때 다음과 같이 multilinearity가 성립함을 확인할 수 있다.
(\lambda_1u_1+\lambda_2u_2,\lambda_1v_1+\lambda_2v_2)^w=\lambda_1(u_1,v_1)^w+\lambda_2(u_2,v_2)^w

이제 원래 문제로 돌아간다. 그러면 w=\epsilon_1 \cdots \epsilon_{n-1}이라 하면 a_n=(1,7)^w, b_n=(1,7)^{\bar{w}}가 성립한다. 이제 w의 길이에 대한 수학적 귀납법을 적용한다. 길이가 0이나 1인 경우는 자명하고 n \geq 2라 가정하자. 여기서 주로 쓰이게 되는 사실은 바로 \sigma가 0이든 1이든 (2,1)^{\sigma}=7이 성립한다는 것이다. 따라서 \epsilon=0인 경우 (1,7)^{w\sigma 0}=2(1,7)^w+3(1,7)^{w\sigma}=2(1,7)^{\bar{w}}+3(1,7)^{\sigma \bar{w}}=2(2,1)^{\sigma \bar{w}}+3(1,7)^{\sigma \bar{w}}=(7,23)^{\sigma \bar{w}}=(1,7)^{0\sigma \bar{w}}가 성립한다. 마찬가지로 \epsilon=1인 경우도 해결할 수 있다.

사실 (u,v)^w라는 꼴을 써야할 필요는 없이, 수학적 귀납법을 이용하여 길게 표현할 수 있다. 그러나 저 표현법이 실제로 매우 효율적이고 직관적이다. 결론적으로 풀다보면 결국 푸는 본질적 방향은 다들 비슷함을 알 수 있다. 흥미로운 문제.

(사실 왜 C인진 잘 모르겠다 ㅠ A로 놔도 할 말 없고 N으로 놓으면 조금 의아해도 원래 N에 수열 많으니까 할 말 없지만 C는 흠.. 점화식이라서?)

Advertisements
  1. July 19th, 2010

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: