2012 IMO Shortlist의 풀이이다. 앞으로 각 연도의 것들에 대한 해설을 작성할 것인데...아마 대부분은 IMO 공식 홈페이지에 있는 솔루션들을 번역한 것이 될 것이다. International Mathematical Olympiad (imo-official.org) 참조. 다만, 내 풀이가 존재하는 경우도 있을 것이며 대부분의 문제에서 찾을 수 있는 포인트등을 정리할 것이다. 아마 수학을 공부하고자 하지만 영어로 된 오피셜 솔루션에 가로막히는 경우 요긴하게 쓸 수 있지 않을까 싶다.(계속 작성중. 풀이가 추가되는 순서는 내맘대로다.)
A1. 다음 조건을 만족하는 함수 f를 구하여라.
$$f:Z\to Z, f(a)^2+f(b)^2+f(c)^2=2f(a)f(b)+2f(b)f(c)+2f(c)f(a), a+b+c=0$$
우선, 해당 함수방정식에 특정 값을 대입하는 것을 다음과 같이 표현하자: $$P(a,b,c)$$ 우선, P(0,0,0)에 의해 f(0)=0임을 알 수 있다. 이제 P(-a,a,0)을 생각해보면 적절한 식정리에 의해 P(-a)=P(a)라는 사실을 알 수 있다. 어떤 t에 대해 f(t)=0인 경우를 생각해보면, P(a,-a-t,t)에 의해 다음이 성립한다. $$f(a)^2+f(-a-t)^2=2f(0)f(-a-t), f(a)=f(a+t)$$ 따라서 이 경우 t가 0이 아니라면 t는 이 함수의 주기가 된다.
1. f(1)=0일 때, 1이 f의 주기가 되므로 f는 상수함수가 되며, 이를 만족하기 위해 f는 영함수여야 한다. 따라서 다음의 함수가 해가 된다. $$f(n)=0$$
2. f(1)=k이며, k가 0이 아니라고 하자.
2-1. f(2)=0이라면, 해당 함수는 2-주기성에 의해 다음과 같이 나타날 수 있다. $$f(n)=0(2|n),k(2\nmid n)$$(수식 작성의 어려움으로 가독성이 떨어질 수 있습니다.)
2-2. f(2)가 0이 아니라면, P(1,1,2)에 의해 f(2)=4k가 되고, P(t,t,-2t)에 의해 f(2t)는 4f(t) 혹은 0이 된다는 사실을 알 수 있다.
2-2-1. f(4)=0, 이 경우의 함수는 다음과 같이 나타난다. $$f(n)=0(4|n),k(2\nmid n),4k(2|n,4\nmid n)$$ (알수없는 이유로 수식작성이 안되어 방치)
2-2-2. f(4)가 0이 아니라면, 2-2의 논의에 의해 f(4)=16k가 된다. P(1,2,-3)에 의해 f(3)은 k 혹은 9k가 됨을 알 수 있는데, P(1,3,-4)를 계산해보면 f(3)이 9k 혹은 25k이므로 f(3)=9k이다. 이 시점에서 f(n)=kn^2가 해가 될 것이라고 추론할 수 있고, 실제로 이를 귀납적으로 증명 가능하다. f(3)을 계산한것과 동일한 벙법을 전개하기 위해서, P(n,1,-n-1)과 P(n-1,2,-n-1)을 계산하면 f(n+1)의 값이 k(n+1)^2임을 증명 가능하다. 따라서 다음의 함수가 해가 된다. $$f(n)=kn^2$$
comment. 이 문제의 핵심적인 추론과정은 아무래도 3변수 이상이며, 변수의 결정이 서로 독립적이기 때문에 초기항들만 몇개를 설정해주면 다른 값들이 무조건 계산 가능하다는 점이라고 생각한다.
A2. Z와 Q를 각각 정수집합과 유리수 집합이라 하자.
a)Z의 적절한 분할 A,B,C가 존재해서 A+B,B+C,C+A들이 쌍마다 교집합이 없도록 할 수 있는가?
b)Q의 적절한 분할 A,B,C가 존재해서 A+B,B+C,C+A들이 쌍마다 교집합이 없도록 할 수 있는가?
a) 가능하다. 법 3에 대한 값으로 분류하면 된다.
b) 불가능하다.
(sol 1)
가능을 가정하자. 임의의 A,B의 원소 a,b에 대해서, a+b는 A+B의 원소이다. 만약 a+b-c(c는 C의 원소)가 A 혹은 B에 포함되었다면, a+b-c+c는 (A or B)+C에 포함되는데, 이는 a+b가 A+B의 원소임에 모순이다. 따라서 a+b-c는 C의 원소이고, 따라서 임의의 a+b는 C+C의 원소이다. 즉, A+B가 C+C의 부분집합이고, 유사한 관계들도 성립한다. 이제 A의 두 원소 a1,a2를 생각할 것인데, a1+a2-b=a1+(a2+c-b)-c이고 a1, (a2+c-b),c가 각각 A,B,C의 원소이므로 a1+a2는 C의 원소이다. 즉, A+A가 B+C의 부분집합이며, 앞선 논의로 인해 A+A=B+C가 되고 유사한 관계도 성립한다. 이제 일반성을 잃지 않고 0이 A의 원소라고 하자. B+C는 A+C, A+B와 교집합이 없는데, A에 0이 존재하므로 B+C와 B,C 사이에도 교집합이 없게 된다. 즉, B+C의 모든 원소가 A에 속하기 때문에 B+C는 A의 부분집합이 된다. 그런데 A는 A+A의 부분집합이기 때문에, 다음 식 때문에 A=A+A가 된다. $$A=\left\{ 0 \right\}+A\subset A+A=B+C\subset A$$
여기서 A+A+A=A=B+B+B=C+C+C=A+B+C라는 사실을 알 수 있다. 이는 곧 임의의 원소를 가져왔을 때 그것의 3배가 A에 속한다는 것인데, 만약 어떤 원소가 B 혹은 C에 포함된다면 그것을 3으로 나눈 것 또한 유리수이므로 모순이 발생해서 A가 Q 전체가 되는데, 이는 모순이다.
(sol 2)
두 번째 풀이는 귀찮아서 안한다.
comment(official). 정수 집합에서 해의 유일성도 첫 풀이를 통해 증명이 가능한데, 유리수에서 모순을 일으키는 방법은 가장 마지막에만 그 성질을 사용했기 때문에 많은 논의가 정수 집합으로도 확장 가능하다.
A6. 다음 조건을 만족하는 f:N->N을 생각하자: 임의의 n에 대해서 f^2k(n)=n+2k인 양의 정수 k가 존재한다. 또한, 각 n에 대해서 그러한 k의 최솟값을 k_n이라 하자. k가 유계가 아님을 보이시오.
이 문제는 개인적으로 정말 좋아하는 문제중 하나이다. 가끔 이러한 문제들에 사용되곤 하는 chain이라는 아이디어에 대한 좋은 intuition이 되기 때문이다.(작성 예정)
C1. 몇개의 양의 정수가 일렬로 나열되어있다. 앨리스는 이중 이웃한 x>y를 잡은 다음, 이를 (y+1,x) 혹은 (x-1,x)로 바꾼다. 이 시행을 무한히 시행할 수 없음을 보여라.
각 솔루션들이 시행 횟수의 서로 다른 bound를 제시하고 있다.
(sol 1)
f(a1,...,an)=a1+2a2+...+nan으로 정의하고 나면, 각 시행마다 f가 증가함을 알 수 있다. 그러나 각 시행마다 a1~an중 최댓값의 크기는 늘어나지 않기 때문에, 그 최댓값을 M이라고 하면 시행 횟수의 bound는 다음과 같다: $$(1+...+n)M$$
(sol 2)
각 수열들에서 가장 마지막 수들을 비교해가며, 더 큰 것이 최초로 나온 수열이 "더 크다"고 정의하자. 이러한 것은 사전식 배열과도 연관이 있다. 아무튼, 이러한 정의는 추이성을 만족한다. 즉, a<b이고 b<c이면 a<c임을 만족하는데, 이에 대한 증명은 생략한다. 위에서 관찰한 내용인, 시행을 거쳐도 최댓값의 크기가 변하지 않는다는 점을 적용하면 각 시행이 서로 다른 수열을 만들어야 하므로, 가능한 시행수는 다음과 bound를 가진다: $$M^n$$
(sol 3)
해당 풀이는 sol 2와 어느정도 유사한 맥락을 가진다. 각 수열 a=(a1,a2,...)에 대해, s=(s1,s2,...)를 정의하는데, si는 ai보다 작은 a의 모든 원소의 개수로 정의한다. 이제 a의 s를 a'과 s'으로 시행을 통해 바꾼 경우를 생각하면, (x,y)가 (y+1,x-1)로 변형된 것인데, 이 관계를 적당히 따져보면 s'이 s에 비해 사전순으로 앞선다는 사실을 알 수 있다. s의 원소의 최댓값은 n정도로 bound되어있기 때문에, 시행수의 bound는 다음과 같다: $$n^n$$
comment. 사실 가장 직관적인 풀이는 sol 1이라고 생각된다. 이렇게 어떤 조합론적인 상황에서 특정 개체에게 가중치를 부여해서, 그 합의 단조성을 보이는 기법을 자주 보았기 때문에 숙달될 필요가 있다고 생각된다. 또한, sol 2,3에서는 사전식 배열이라는 아이디어를 적용하였는데, 이것도 어떻게 보면 가중치와 단조성의 연장선상인 것 같다.
C2. 1,...,n을 적절한 두 정수의 쌍으로 묶어서 각 쌍의 수들의 합이 n을 넘지 않고 쌍마다 다른 값을 가지도록 하려고 한다. 가능한 쌍의 개수의 최댓값을 구하여라.
x개의 쌍으로 나누었다고 생각하자. 우선, 1,...,2x까지의 전체합은 2x개의 수의 합보다는 자명히 큰데, 쌍마다 다른 값을 가지고 n보다 작거나 같다고 했으므로 그 값은 n+n-1+...+(n-x+1)보다 작거나 같다. 이 식을 잘 풀면 다음과 같은 bound를 얻는다: $$x\le \left\lfloor \frac{2n-1}{5} \right\rfloor$$ 이제 적당히 실례를 construct하면 되는데, 대충 등차수열 느낌으로 적당히 분류하면 풀린다.
comment. 딱히 쓸게 없긴 한데...굳이 말하자면 어떤 실례를 등차수열? 혹은 일정한 규칙성을 가진 대상으로 잡는 것은 모든 문제에서 통용되는 방법인 것 같다.
C7. 원 위에 2^500개의 점이 있고, 각 점에 1~2^500까지의 서로다른 숫자가 적혀있다. 이때, 적절한 100개의 현이 존재해서, 현의 양 끝의 합이 같고, 서로 교차하지 않도록 하는것이 가능함을 보여라.
이 문제는 후술할 보조정리의 좋은 intuition이 된다고 생각한다. 우선, 풀이에 앞서 어떤 그래프의 최대 독립 집합이라는 것은 적절한 점들을 선택해서, 그 집합 사이의 어떤 정점들 사이에도 간선이 존재하지 않도록 하는 가장 큰 집합이다. 그래프를 반전한 다음 clique를 구하는 문제와 동일하다. 이러한 문제는 일반적으로 아마도 NP-hard겠지만, 이것에 대한 쓸만한 bound가 존재한다.
(lemma) f(G)를 G의 최대 독립 집합의 크기로 정의하자. 다음이 성립한다. $$f(G)\ge \sum_{v\in G}^{}\frac{1}{deg v+1}$$
pf) 정점 개수 귀납을 적용하자. 가장 차수가 작은 정점을 v라 하고, 그 차수를 d, v가 v1,...,vd와 연결되어있다고 하자. v1~vd를 전부 제거한 그래프를 G'이라 하면 $$f(G)\gef(G')+1\ge\sum_{v\in G'}^{}\frac{1}{deg v+1}+frac{d+1}{d+1}\ge\sum_{v\in G}^{}\frac{1}{deg v+1}$$이므로 성립한다. (Q.E.D 증명완료)
이제 합이 i인 현들을 정점으로 하고, 각 현들이 교차할 때 간선을 그은 그래프를 Gi라고 하자. 또한 논의의 편의를 위해 n=2^499라고 하자. 이때, 만약 어떤 현 사이에 k개의 점이 있었다면 그 현의 차수는 최대 k이다. 이런 관찰들을 바탕으로 정리하면,$$\sum_{i=1}^{4n-3}f(G_i)\ge \sum_{i=1}^{4n-3}\sum_{v\in G_i}^{}\frac{1}{degv+1}\ge \sum_{i=1}^{n-2}\frac{1}{i+1}\times 2n$$이 되고, 조화수열의 적절한 성질을 활용하거나 혹은 2^n으로 잘 bound하면 가장 오른쪽의 합 부분이 200 이상임을 증명할 수 있고, 여기에서 비둘기집의 원리를 적용하면 문제가 해결된다.
comment. 이 문제는 비교적 풀이가 단순함에도 불구하고 C7이라는 난이도를 부여받았는데, 이는 즉 lemma를 알고 있는것도 난이도가 있는 마당에 발상 난이도도 매우 어렵기 때문이다. 이런 정리를 아는 것이 힘이 된다는걸 다시 한번 알려주는 문제였다.
N8. 100 초과의 소수 p에 대해서, 그리고 모든 정수 r에 대해서 p가 a^2+b^5-r을 나누는 a,b가 항상 존재함을 증명하라.
2개의 풀이가 있는데, 둘 다 좋은 풀이라고 생각된다.
(sol 1) 모든 합동산술은 p 기준이다. 다음과 같은 조건을 만족하는 4개의 정수의 순서쌍 (a,b,c,d)에 대해 분석하자(a,b,c,d<p):$$a^2+b^5\equiv c^2+b^5$$
이 조건을 만족하는 모든 순서쌍의 개수를 N이라 하자.
lemma) $$N\le p(p^2+4p-4)$$
pf)
1. 첫번째로 b^5===d^5인 경우를 보자. 이런 조건을 만족하는 (b,d)의 개수를 k라 하자. b=0이면 d=0이며, 그렇지 않은 b에 대해 d는 최대 5개 존재한다. 즉, k<=5p-4이다. 또한, 이런 b,d에 대해 a,c는 비슷한 방법으로 2p-1개 있다.
2. b^5와 d^5가 합동이 아니라면? (a-c)(a+c)=d^5-b^5인데, 그렇다면 각 a-c에 대해 a+c는 유일하게 결정되고 이를 통해 a,c를 알 수 있다. 즉, 쌍의 개수는 p-1개가 된다.
따라서, N=k(2p-1)+(p^2-k)(p-1)=p^2(p-1)+kp<=p^2(p-1)+(5p-4)p=p(p^2+4p-4)가 되어 명제가 성립한다.
이제, 만약 어떤 r에 대해서 a,b가 존재하지 않았다고 하자. 그렇다면 어떤 x에 대해서, r*x^10 또한 표현이 불가능함을 쉽게 증명할 수 있다. 그런데 p가 100 초과이므로 x를 원시근으로 잡고 나면, 적어도 4개의 r은 표현이 불가능해진다. 여기서 한가지 더 중요한 관찰을 하는데, s_r을 r을 표현하는 방법의 수로 정의하면 N은 각 s_i의 제곱의 합이라는 것이다. 그 증명은 매우 자명하므로 생략한다. 그렇다면 다음과 같은 식에 의해 모순이 나타난다:$$N=\sum_{i=0}^{p-1}s_i^2\ge \frac{1}{p-4}(\sum_{i=0}^{p-1}s_r)^2=\frac{p^4}{p-4}\gt p(p^2+4p-4)$$
여기서 첫번째 부등식은 코시에 의해 성립한다.
(sol 2) 이 풀이에서는 보다 직관적으로 원시근을 통해 문제를 해결하고, 이는 범용성도 높아 굳이 5제곱을 고수할 필요가 없다(사실 위 풀이도 그렇긴 할 것이다.)
만약 p가 10k+1꼴이 아니라면, b^5과 a^2중 하나는 각 숫자마다 서로 다른 값을 내게 되고, 결과적으로 법 p에 대한 완전잉여계를 이루기 때문에 문제가 해결된다. 따라서, p를 10k+1꼴의 소수로 가정하고 g를 그 원시근이라 하자. 다음과 같은 사실이 성립한다:$$g^\frac{p-1}{2}\equiv -1, \sum_{2k-1}^{i=0}g^5di\equiv \begin{cases}2k&(2k|d) \\ 0&(2k\nmid d)\end{cases}$$
해당 명제들의 증명은 연습문제로 남긴다. 이제 어떤 r이 표현될 수 없었다고 가정하자. 자명히 r은 0이 아니며, 첫 번째 사실에 의해 (r-b^5)^((p-1)/2)=(r-b^5)^(5k)=-1(mod p)가 된다. 이제, 각 t=1,...,k-1에 대해 S(t)를 다음과 같이 정의하자:$$S(t)=\sum_{i=0}^{2k-1}(r-g^{5i})^{5k}g^{5ti}$$
이 합은 앞선 관찰들과 2k가 t를 나눌 수 없다는 점에 따라, 다음과 같은 식으로 정리할 수 있다:$$S(t)=\sum_{i=0}^{2k-1}(r-g^{5i})^{5k}g^{5ti}\equiv \sum_{i=0}^{2k-1}(-1)g^{5ti}\equiv 0(mod p)$$
반면, 이 합을 이항계수를 통해 다르게 표현해보면 다음과 같이 정리할 수 있다:$$S(t)=\sum_{i=0}^{2k-1}(\sum_{j=0}^{5k}\binom{5k}{j}r^{5k-j}(-g^{5i})^j)g^{5ti}=\sum_{j=0}^{5k}(-1)^j\binom{5k}{j}r^{5k-j}(\sum_{i=0}^{2k-1}g^{5(j+t)i})\equiv \sum_{j=0}^{5k}(-1)^j\binom{5k}{j}r^{5k-j}\begin{cases}2k&2k|j+t\\ 0&2k\nmid j+t\end{cases}(mod p)$$
그런데, j+t는 6k보다 작기 때문에 2k가 j+t를 나누는 때는 오직 j=2k-t,4k-t일 때 뿐이다. 즉, S(t)라는 값은 다음과 같이 쓸 수 있다: $$S(t)\equiv (-1)^t(\binom{5k}{2k-t}r^{3k+t}+\binom{5k}{4k-t}r^{k+t})\times 2k(mod p)$$
이 식은 모든 t에 대해 성립하기 때문에, 이제 목표는 이 값이 0이 아니게 되는 t가 존재함을 보여 모순을 일으키는 것이 된다. t에 1,2를 대입한 다음, 적절한 계수를 곱해 r을 제거해주면 모순을 낼 수 있는데, 이는 연습문제로 남긴다. 따라서 모순이 나타나게 된다.
comment 1(official). p=11을 제외한 모든 10k+1꼴의 수에 대해서 해당 명제가 성립하는데, p=11이면 r=7이라는 반례가 존재한다.
comment 2(official). 이런 풀이가 5라는 숫자의 특수성을 쓰지 않았기 때문에, 5를 임의의 정수로 바꾸어도 해결될 수 있으며, 실제로 충분히 큰 소수에 대해 그러한 결론이 성립한다. 이와 관련되어 더욱 일반적인 결론이 성립한다고 하는데, Hasse-Weil bound?라는게 있는듯 하다.
comment. 이 문제는 사실 풀리는게 신기하다고 느낄수도 있고 실제로 나도 풀이의 핵심을 간파하기 힘들었다. 굳이 꼽자면 정수에서 어떤 값들의 누적합을 구하는 아이디어?는 꽤 쓸만한 것 같다. 1번 풀이도 어느정도 괜찮은 아이디어가 사용되었는데, 어떤 순서쌍의 개수를 구하는 과정에서 저것을 제곱의 합으로 표현할 생각을 하는 것이 인상적인 것 같다. 실제로 저러한 방식으로 유사하게 풀리는 문제가 존재하기 때문에, 어떤 수들의 제곱의 합? 같이 분석하기 비교적 까다로울 수 있는 것들에 대해서는 이렇게 푸는게 좋은 것 같다.
'수학문제' 카테고리의 다른 글
| 2019 APMO 풀이 (3) | 2023.03.02 |
|---|
