2010 KMO #8

이차잉여인간과 함께하는 이차잉여 문제!

8. 원탁에 2010명의 사람이 둥글게 앉아 있다. 어떤 사람에게 과자를 주고, 그 사람으로부터 시계방향으로 1번째, 1+2번째, 1+2+3번째, …, 1+2+…+2009번째 사람에게 과자를 주었다. 이 때, 과자를 하나 이상 받은 사람의 수를 구하여라.

이런 문제도 예전에 어디선가 봤었는데..

각설 답은 408개. 사실 이런 문제는 2010 대신 더 작은 수를 대입해서 앞에 몇 개 좀 해보면 바로 감이 잡히기 마련. mod 2010으로 \frac{n(n+1)}{2}들이 총 몇 개 나오는지를 구하는 문제이다. 이들은 \frac{n(n+1)}{2} = \frac{(2n+1)^2-1}{8}이므로 홀수의 제곱수들과 연관이 깊다.

먼저 mod 1005로 이차잉여가 몇 개있는지를 본다. 이건 중국인의 나머지 정리가 해결해준다. 다행히도 1005는 홀수인 소수들의 곱으로 무승수이다. (3, 5, 67의 곱) 홀수의 소수에 대해선 이차잉여가 어떻게 나오는지 잘 안다. 구체적으로 p가 홀수인 소수이면 이차잉여\frac{p+1}{2}개가 나온다. 그러면 서로 다른 홀수 소수 p,q에 대해 mod pq이차잉여는 몇 개인가? \frac{p+1}{2}\frac{q+1}{2}가 된다. 왜냐면 먼저 pq에 대해 이차잉여인 것은 mod p나 mod q로 봐도 이차잉여가 되어야 하고, 역으로 mod p이차잉여 하나 택해 x라 하고 mod q이차잉여 하나 택해 y라 하면 a^2 \equiv x\text{ (mod }p\text{)}, b^2 \equiv y\text{ (mod }q\text{)}a,b를 찾을 수 있고, 그러면 c \equiv a\text{ (mod }p\text{)}, c \equiv b\text{ (mod }q\text{)}c를 mod pq에서 찾으면 x,y에 해당되는 mod pq의 이차잉여를 찾을 수 있기 때문이다. 마찬가지로 생각하면, mod 1005로 이차잉여의 개수는 2 \cdot 3 \cdot 34=204개가 된다.

한 편, 홀수 k에 대해 mod k이차잉여 개수를 q라 하자. (현재 k=1005, q=204) 그러면 우리가 관심있는 것은 홀수인 이차잉여 mod 2k이므로 x^2 \equiv 1\text{ (mod }2\text{)}x^2 \equiv 0^2,1^2,\cdots\text{ (mod }k\text{)}의 해를 찾으면 되는데 앞의 것의 해는 x \equiv 1\text{ (mod }2\text{)}밖에 없으므로 개수는 그냥 q가 된다. 그럼 이런 홀수 제곱수들에서 1을 뺀 후 8로 나눈 것들을 봐야하는데, 1로 빼면 짝수들 mod 2k이고, 2로 먼저 나누면 어떤 수들 mod k가 된다. (not 2k) 그러면 하나 더 확인해줘야할 사실은 임의의 a에 대해 \frac{a(a+1)}{2} \equiv k+ \frac{b(b+1)}{2}\text{ (mod }2k\text{)}b가 존재하겠냐는 것. 그런 b2k-a-1로 넣으면 된다.

즉, 각각의 홀수 이차잉여 mod 2k마다 1을 빼주고 2로 나누면 그 값들은 mod k로 총 q개가 나오고, 이를 mod 2k로 볼 때에 각각의 수들은 그 수와 그 수에 k를 더한 것 모두 나오게 되어 총 개수는 2q가 된다. 따라서 답은 2q=408.

깔끔하고 좋은 문제이긴 한데, 어디서 봤던 것 같은데 흠..

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: