Posts Tagged ‘ 이항계수 ’

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 대표애들과 같이 푸는데 대략 사흘 정도를 아무도 해결하지 못한 채로 넘겼다. 사실은 이 풀이도 누군가가 풀어서 알게된 것이 아니라 오피셜을 주워 들은 것이라..

Advertisements