Posts Tagged ‘ USA TST ’

2010 USA TST #8

다음은 앞에서 올린 2010 USA TST의 한 문제이다.

8. m \geq n이 자연수이며 Sa_1+a_2+\cdots+a_n=m인 양의 정수쌍 (a_1,a_2,\cdots,a_n)의 집합이라 하자. 이 때, 다음 등식이 성립함을 보여라.

\displaystyle \sum_{S}1^{a_1}2^{a_2}\cdots n^{a_n}=\binom{n}{n}n^m-\binom{n}{n-1}(n-1)^m+\cdots+(-1)^{n-2}\binom{n}{2}2^m+(-1)^{n-1}\binom{n}{1}

이 식은 간단히 써서 \displaystyle \sum_{a_1+\cdots+a_n=m}1^{a_1}2^{a_2}\cdots n^{a_n}=\sum_{i=0}^{n} \binom{n}{i}(-1)^i (n-i)^m이라 할 수 있다.

First Solution. 순수하게 생성함수만을 이용하여 문제를 풀어보자.
좌변에 대한 생성함수인 \displaystyle \sum_{m=1}^{\infty}\sum_{a_1+\cdots+a_n=m}1^{a_1}2^{a_2}\cdots n^{a_n} x^m을 표현하자. 이는 \displaystyle \sum_{m \geq 1} \sum_{a_i} (1x)^{a_1}(2x)^{a_2} \cdots (nx)^{a_n}, 즉 \frac{x}{1-x}\frac{2x}{1-2x} \cdots \frac{nx}{1-nx}=\frac{n!x^n}{(1-x)(1-2x)\cdots (1-nx)}가 된다.

한 편, 우변의 생성함수는
\displaystyle \sum_{m=1}^{\infty}\sum_{i=0}^{n-1} \binom{n}{i} (-1)^i (n-i)^m x^m =\sum_{i=0}^{n-1}\sum_{m=1}^{\infty} \binom{n}{i} (-1)^i (n-i)^m x^m
\displaystyle =\sum_{i=0}^{n-1}\binom{n}{i}(-1)^i \sum_{m=1}^{\infty} ((n-i)x)^m =\sum_{i=0}^{n-1}\binom{n}{i}(-1)^i \frac{(n-i)x}{1-(n-i)x}
\displaystyle =\sum_{i=0}^{n-1}\binom{n}{n-i}(-1)^i \frac{(n-i)x}{1-(n-i)x} =\sum_{i=0}^{n-1}n \binom{n-1}{n-i-1}(-1)^i \frac{x}{1-(n-i)x}
\displaystyle =nx\sum_{i=0}^{n-1}\binom{n-1}{i}(-1)^i \frac{1}{1-(n-i)x}가 되므로,
\displaystyle \frac{(n-1)!x^{n-1}}{(1-x)(1-2x)\cdots (1-nx)} = \sum_{i=0}^{n-1} \binom{n-1}{i}(-1)^i \frac{1}{1-(n-i)x}
임을 확인하면 된다. 이는 곧
\displaystyle (n-1)!x^{n-1} = \sum_{i=0}^{n-1} \binom{n-1}{i}(-1)^i \frac{(1-x)(1-2x)\cdots(1-nx)}{1-(n-i)x}
임을 확인하는 것인데, 양변이 둘 다 차수가 n-1차인 다항식이므로 n개의 x의 값에 대해 양변이 일치하면 된다. 이제 1 \leq k \leq n에 대해 x=\frac{1}{k}를 대입하자. 그러면 좌변은 \frac{(n-1)!}{k^{n-1}}이고 우변은 i=n-k에 해당하는 항을 제외하곤 전부 소거되고 n-k번째 항인 \displaystyle \binom{n-1}{n-k}(-1)^{n-k}(1-\frac{1}{k})(1-\frac{2}{k}\cdots(1-\frac{k-1}{k})(1-\frac{k+1}{k})\cdots(1-\frac{n}{k})만 남는다. 이는 정리하면 \displaystyle \frac{(n-1)!}{(n-k)!(k-1)!}(-1)^{n-k}\frac{(k-1)(k-2) \cdots 1 (-1)(-2) \cdots (-(n-k))}{k^{n-1}} = \frac{(n-1)!}{k^{n-1}}이 된다. 따라서 문제가 증명된다.

사실 가장 먼저 발견한 풀이는 다음 semi-combinatorial한 풀이였다. 우변을 보자마자 전사함수 개수를 떠올려버려서, 거의 10분만에 풀었다. -_-;; 위의 생성함수 풀이는 그 후에 발견한 풀이.

Second Solution. 이번엔 조합적으로 식을 해석한다. 먼저 우변은 포함과 배제의 원리를 이용하여 원소의 개수가 m개인 집합에서 n개인 집합으로 가는 전사함수의 개수임을 확인할 수 있다. 한 편 좌변의 생성함수는 \displaystyle \frac{n!x^n}{(1-x)(1-2x)\cdots (1-nx)}임을 앞 풀이에서 이미 확인했다. 그런데 이것의 x^m의 계수는 바로 n!(S(m,n)), 즉 제2스털링 수이다. 이것은 m개짜리 집합을 n개의 공집합 아닌 집합들로 나누는 분할의 가지수에 n!을 곱한 것이다. 이는 이렇게 해석해볼 수 있다. 먼저 정의역의 m개의 원소들을 n개의 부분집합들로 분할한 후, 각각의 부분집합이 치역의 어느 원소로 대응될지를 결정하는 것이다. 앞의 경우의 수가 S(m,n)이고 뒤의 경우의 수가 n!이므로 문제는 증명된다.

그런데 제2스털링수가 나오니, 예전에 Enumerative Combinatorics Vol. 1을 공부하다가 제2스털링수와 관련된 일대일대응을 배운 것이 기억나서 순수 조합적인 풀이를 찾으려 노력했고 그 결과는 다음과 같다.

Third Solution. 앞에서 해결한 바와 같이 우변은 원소가 m개인 집합에서 n개인 집합으로 가는 전사함수의 개수이고, 이는 곧 원소가 m개인 집합을 n개의 부분집합으로 분할한 후 n!을 곱한 값과 같다. 이런 분할마다 다음과 같이 m의 분합(composition)으로 대응하자. a_n+\cdots+a_{n-i+1}집합의 분할에서 1,2,\cdots,r을 없앴을 때 남은 부분집합의 개수가 (공집합 제외) n-i개가 되도록 하는 최소의 r 정의한다. 예컨대, m=4,n=2의 한 예인 \{ 1,3 \}, \{ 2,4 \}의 경우 1,2,3을 지워야 비로소 한 개의 부분집합만 남게 되므로 a_2=3, a_1+a_2=4(a_1,a_2)=(1,3)을 얻는다. 이 때 m의 한 분합 (a_1,\cdots,a_n)에 대해 이것으로 대응되는 분할의 개수를 생각한다. 이는 다음과 같이 생각하자. 먼저 n부터 차례대로 써 넣는다. n을 쓰고 나서 n-1부터는 어느 부분집합으로 갈지 결정해야 한다. 이 때 n-a에서 n-a_1+1까지는 한 부분집합만을 쓰므로 그 가지수는 1^{a_1-1}이다. 한 편 n-a_1은 반드시 새로운 부분집합을 만들어야 한다. 그리고 n-a_1-1부터 n-a_1-a_2+1까지는 두 부분집합에서 결정해야 하므로 가지수는 2^{a_2-1}이다. 마찬가지로 계속 하다보면 한 분합 (a_1,\cdots,a_n)으로 대응되는 분할의 개수가 1^{a_1-1}\cdots n^{a_n-1}이 된다. 즉 전사함수의 개수는 \displaystyle n! \sum_{a_1+\cdots+a_n=m} a^{a_1-1}\cdots n^{a_n-1}=\sum_{a_1+\cdots+a_n=m} a^{a_1}\cdots n^{a_n}, 즉 좌변이 되어 증명이 끝난다.

약간 우회한 감이 없지 않다. 밑의 풀이는 오피셜 솔루션이라 하는데, 본질은 결국 위의 세 번째 풀이랑 똑같지만 서술하는 과정이 훨씬 깔끔하다.

Fourth Solution. 역시 우변은 전사함수의 개수이다. 이는 곧 1,2,\cdots,n을 이용하여 길이가 m인 수열을 만들되 1,2,\cdots,n이 한 번 이상 들어가도록 하는 개수와 같다. 이제 맨 처음부터 봤을 때 새로운 숫자가 나올 때마다 표시를 해준다. 예컨대, m=10,n=5일 때에 2,2,3,2,3,1,4,3,4,4란 수열이 있으면 (2),2,(3),2,3,(1),(4),3,4,4와 같이 표시를 한다. 이 때 i번째 새로운 수가 나오는 위치를 a_1+a_2+\cdots+a_{i-1}+1이라 한다. 그리고 a_n=m-(a_1+\cdots+a_{n-1})로 정의한다. (이 예의 경우 a_1=2,a_2=3,a_3=1,a_4=4이다.) 그러면 표시한 곳들에는 1,2,\cdots,n이 들어가야 하므로 그 순서를 택하는 가지수가 n!이다. 그리고 첫 번째 표시에서 두 번째 표시 사이에는 한 가지 숫자만 들어가므로 가지수는 1^{a_1-1}가지이고, 두 번째 표시에서 세 번째 표시 사이에는 두 가지 숫자만 들어가므로 가지수는 2^{a_2-1}가지이고, …, 이런 식으로 계속 하면 결국 우변의 값은 \displaystyle n! \sum_{a_1+\cdots+a_n=m} a^{a_1-1}\cdots n^{a_n-1}=\sum_{a_1+\cdots+a_n=m} a^{a_1}\cdots n^{a_n}, 즉 좌변이 되어 증명이 끝난다.

Any other solutions?

Advertisements

2010 USA TST

2010년 미국 최종 선발 시험. 2010년 6월 10일~12일. 하루에 네 시간 반 3문제로 총 사흘.

1. 정수계수 다항식 P(x)P(0)=0\gcd(P(0),P(1),P(2),\cdots)=1을 만족한다고 하자. 이 때 다음을 만족시키는 양의 정수 n이 무수히 많음을 보여라.

\gcd(P(n)-P(0),P(n+1)-P(1),P(n+2)-P(2),\cdots)=n

2. abc=1인 양수 a,b,c에 대해 다음 부등식이 성립함을 보여라.

\displaystyle \sum_{cyc} \frac{1}{a^5 (b+2c)^2} \geq \frac{1}{3}

3. 예각 삼각형 ABC의 높이를 각각 h_a,h_b,h_c라 하자. ABC 내부의 임의의 점 P에 대해 다음 부등식이 성립함을 보여라.

\displaystyle \sum_{cyc}\frac{PA}{h_b+h_c}\geq 1

4. 삼각형 ABC의 변 AC,BC 위에 각각 점 M,N이 놓여 있어 MNBC가 평행하다고 한다. 변 AB,CB 위에 각각 점 P,Q를 잡아 PQAC가 평행이 되도록 하자. 삼각형 CMN의 내접원이 변 AC와 점 E에서 접한다. 삼각형 BPQ의 내접원이 변 ABF에서 접한다. 직선 ENABR에서 만나고, 직선 FQACS에서 만난다. AE=AF이라면, 삼각형 AEF의 내심은 삼각형 ARS의 내접원 위에 옴을 증명하여라.

5. a_1=1이고 a_n=a_{\lfloor n/2 \rfloor}+a_{\lfloor n/3 \rfloor}+\cdots+a_{\lfloor n/n \rfloor}+1인 수열 을 생각하자. 이 때,a_n \equiv n (\text{mod }2^{2010})n이 무수히 많이 존재함을 보여라.

6. T는 1보다 큰 자연수로 이루어진 유한 집합이다. 이제 T의 부분집합 S에 대해, 임의의 t \in T에 대해 \gcd(s,t)>1s \in S가 존재하면 S를 좋은 부분집합이라 하자. (단, S는 공집합이 아니다.) 이 때 좋은 부분집합의 개수는 홀수임을 보여라.

7. 예각 삼각형 ABC의 내부에 점 P,Q가 있어 \angle PAB = \angle QAC\angle PBA = \angle QBC가 성립한다. BC 위의 점 D에 대해 \angle DPC + \angle APB=\pi 임과 \angle DQB + \angle AQC=\pi 가 동치임을 보여라.

8. m \geq n이 자연수이며 Sa_1+a_2+\cdots+a_n=m인 양의 정수쌍 (a_1,a_2,\cdots,a_n)의 집합이라 하자. 이 때, 다음 등식이 성립함을 보여라.

\displaystyle \sum_{S}1^{a_1}2^{a_2}\cdots n^{a_n}=\binom{n}{n}n^m-\binom{n}{n-1}(n-1)^m+\cdots+(-1)^{n-2}\binom{n}{2}2^m+(-1)^{n-1}\binom{n}{1}

9. p=6k+1이 소수이며 \binom{3k}{k}\equiv 1 (\text{mod }p)가 성립하는 양의 정수 k가 존재하는지 판명하여라.

2010 USA TST #9

얼마 전에 Zuming Feng에게서 올해 미국 TST 문제를 받았다. 이번 TST에는 꽤 흥미로운 문제들이 많았는데, 다음 문제가 그 중 하나였다.

p=6k+1이면서 \binom{3k}{k} \equiv 1 (\text{mod } p)인 소수 p는 존재하는가?

이 문제가 생각보다 어렵다. 사실 넘버링에서 알 수 있듯이, 9번이라 함은 세 번째 날의 3번, 즉 어려운 포지션에 해당되는 문제인데, 평소 알고 있는 접근법으로 시도하면 많은 방법으론 실패함을 깨달을 수 있다. 이 문제의 풀이는 나중에 공개하도록 하겠다. 한 번 직접 고민해보고 풀이를 찾아보자. 임금님 귀는 당나귀 귀!!!!

키 포인트는 뿌리근이다. 특히 뿌리근이 x^N=1을 만족하는 복소수, 즉 primitive roots of unity들과 비슷한 존재라는 것에 포인트가 있다. 그런데 이걸 어떻게 써먹어야 하는가?

경시 문제를 풀다가 생성함수에서 복소수를 이용하는 경우 가끔 이런 경험이 있을 것이다. f(x)란 생성함수 (혹은 무한급수) 가 주어져 있을 때, f(1)+f(\omega)+f(\omega^2)+\cdots+f(\omega^{N-1})을 계산하면 N의 배수에 해당하는 항들만 남고 나머지는 사라지는 것을 이용하는 것 말이다. 이 아이디어를 조금 확장하여 이 문제에서 응용하기로 한다.

먼저 \text{mod }p의 뿌리근 g를 잡는다. 그리고 \displaystyle \sum_{i=1}^{k} (g^{6i}+1)^{3k}를 계산한다. 페르마의 소정리에 의해 임의의 0이 아닌 수 a에 대해 a^{6k} \equiv 1 (\text{mod }p)이므로 a^{3k} \equiv \pm 1 (\text{mod }p)을 얻는다. 따라서 위의 값은 (\text{mod }6k+1)로 볼 때 -k,-k+1,\cdots,-1,0,1,\cdots,k-1,k가 되어야 한다.

하지만 \displaystyle \sum_{i=1}^{k} (g^{6i}+1)^{3k}을 전개하면, (g^{6i}+1)^{3k}에서 0,k,2k,3k번째를 제외한 나머지 항들은 전부 없어지며 이 네 개의 항들은 k번 더해진다. 곧, \equiv k(\binom{3k}{0}+\binom{3k}{k}+\binom{3k}{2k}+\binom{3k}{3k})가 된다. 따라서 귀류법을 써 \binom{3k}{k} \equiv 1(\text{mod }p)라고 가정하면, 이 값은 (\text{mod }6k+1)4k가 되어야 한다. 이는 앞에서 이 값이 -k,-k+1,\cdots,-1,0,1,\cdots,k-1,k가 되어야 한다고 했으므로, 모순이 나온다.

위에선 담담한 문체로 썼지만, 사실 이 문제 꽤 어렵다. 이 방법을 찾아내는 것이 어려워서. 실제로 이번 2010년 IMO 대표애들과 같이 푸는데 대략 사흘 정도를 아무도 해결하지 못한 채로 넘겼다. 사실은 이 풀이도 누군가가 풀어서 알게된 것이 아니라 오피셜을 주워 들은 것이라..