2019 IMO Problem 4

누군가 2019 IMO 문제지를 던져 줬는데 (어제 시험이 끝났다고 하는데, 이렇게 빨리 공개되는지는 몰랐다), 일단 내 실력으로 상식적인 시간내에 풀수있을 번호는 1번과 4번뿐이고 4번이 정수 문제길래 천천히 풀어보기로 했다. 고등학교때 올림피아드 준비를 했던것도 아니고, 이제막 정수론 공부해보려고 하는 정도라서 엄청 오래 걸렸다;;;

 

문제

다음 조건을 만족하는 양의 정수의 순서쌍 $(k, n)$ 을 모두 구하여라.

$$k!=(2^n - 1)(2^n - 2)(2^n - 4) \cdots (2^n - 2^{n-1})$$

 

---

(스포 방지선)

 

 

 

 

 

 

 

 

 

 

 

 

 

---

풀이

왜 이런 notation을 쓰는지는 잘 모르겠지만, $\nu_{a}(x)$ 는 $x$ 가 $a^{n}$ 으로 나누어 떨어지는 최대의 정수 $n$을 의미한다. (즉, $x$를 소인수 분해했을 때 $a$의 지수) 

이때, $\nu_{p}(k!)$ 를 다음과 같이 쓸 수 있다는 사실은 잘 알려져 있다.

$$\nu_{p}(k!) = \sum_{k = 1}^{\infty} \Big\lfloor\frac{n}{p^k}\Big\rfloor$$

언젠가는 $p^k$가 $n$보다 커질 것이므로 우변은 유한하고, $k$가 무한대까지 갈 때의 무한급수의 합보다 작거나 같다. 즉. 

$$\nu_{p}(k!) \leq \frac{k}{p-1}$$

이 식이 모든 $p$와 $k$에 대해 성립한다.

 

먼저 우변을 잘 관찰해 보면, 첫 항은 2로 나누어 떨어지지 않고, 두 번째는 2로 한 번 나누어 떨어지고... 를 관찰할 수 있다. 따라서, 우변을 다음과 같이 고쳐 쓸 수 있다.

$$k! = 2^{\frac{n(n-1)}{2}} (2-1)(2^2-1)(2^3-1) \cdots (2^n-1)$$

(수식 폰트가 약간 이상한데, $\TeX$가 아닌 mathjax의 한계인듯...?)

 

따라서, $\nu_{2}(k!) = \frac{n(n-1)}{2}$ 이다. 위에서 찾은 부등식을 이용하면, $\frac{n(n-1)}{2} < k$ 이므로, $n(n-1) < 2k$ 이다.

 

이제,  $\nu_3$을 생각해 보자. 

오른쪽에서 앞의 2의 지수항은 어차피 3으로 한번도 나누어 떨어질 수 없으므로, 우리는 $(2-1)(4-1)\cdots (2^n-1)$ 이 3으로 몇 번 나누어 떨어질지만 알면 된다. 먼저 다음의 Lemma를 보자.

---

Lemma (LTE Lemma)

홀수 소수 $p$에 대해, $x - y$ 가 $p$ 로 나누어 떨어지고, $x$와 $y$ 각각은 $p$와 서로소이면, 

$$\nu_p(x^n-y^n) = \nu_p(x-y)+\nu_p(n)$$

 

증명을 이 글에 때려넣기는 매우 길기 때문에, 언젠가 기회가 되면 다루기로 하고 일단은 간략하게 증명 방법만 제시한다. 

참고 자료 : (링크) - Brilliant Wiki, (링크2) - 좀더 Formal하게 잘 정리된 문서. 

증명의 간략한 흐름은 다음과 같다.

먼저, $\nu_p(ab) = \nu_p(a) + \nu_p(b)$ 는 자명하다.

따라서, 인수분해를 해보면, $\nu_p(x-y) + \nu_p(x^{n-1} + x^{n-2}y + \cdots xy^{n-2} + y^{n-1})$ 이다. 

 

만약 $n$이 $p$와 서로소이면, 

$$x^{n-1} + x^{n-2}y + \cdots + xy^{n-2} + y^{n-1}$$ 

이 식이 $p$ 로 나누어 떨어지지 않음을 보일 수 있다. 

 

만약 $n = p$ 이면, 다음이 성립한다.

$$\nu_p(x^n-y^n) = \nu_p(x-y)+1$$

이걸 위해서는 $y = x+pk$ 로 놓고, 다항식을 열심히 전개해 보면 $p$로는 나누어 떨어지지만 $p^2$ 로는 안 된다는 걸 보일 수 있다.

 

다음으로, $n = p^{a} b$ 이고, $b$가 $p$와 서로소일 때는, 식을 잘 전개해 보면 위 두 케이스 중 하나로 잘리고 지수가 줄어든다. 반복해서 우리가 원하는 결과를 얻을 수 있다.

---

위 Lemma를 사용할 수 있는 환경인 것을 어떻게 알 수 있느냐면, 우리는 $2^n - 1$ 이 3으로 나누어 떨어지기 위해서는 $n$이 짝수인 것이 필요충분조건임을 안다. (증명은 어렵지 않은 induction이므로, 생략) 따라서,  $2^{2m} - 1$ 들만이 3으로 나누어 떨어질 수 있으므로,  

$(2-1)(4-1)\cdots (2^n-1)$ 대신 $(4-1)(4^2-1)\cdots (4^{\lfloor\frac{n}{2}\rfloor}-1)$이 3으로 몇 번 나누어 떨어지는지 보는 것으로 충분하다.

$\nu_3(4^t-1) = \nu_3(4^t - 1^t)$ 이므로 

LTE Lemma를 이용할 수 있는 조건이 갖춰지고, $\nu_3(4^t-1) = 1 + \nu_3(t)$ 이다. 

 

즉, 우리가 원하는 값은 다음과 같다. (식이 약간 보기 어렵지만..)

$$\lfloor\frac{n}{2} \rfloor + \sum_{i = 1}^{\lfloor \frac{n}{2}\rfloor} \nu_3(i)$$

 

이제, 오른쪽의 합은 자명하게 $\frac{n}{6} + \frac{n}{18} \dots$ 보다 약간 작을 것임을 쉽게 알 수 있다. (위와 같은 논리로, 무한급수에서 유한개만큼 끊어낸 부분이니까)

또한, 왼쪽도 $\frac{n}{2}$ 보다 약간 작다.

따라서, 우리가 원하는 값은 적어도 다음 무한급수의 합보다 작다.

$$\frac{n}{2} + \frac{n}{6} \cdots = \frac{3n}{4}$$

 

거의 다 왔다. 마지막으로, $\nu_3(k!)$을 생각해 보면, $\lfloor\frac{k}{3}\rfloor + \lfloor\frac{k}{9}\rfloor \dots$ 이므로, $\frac{k}{3} - 1$ 보다는 크거나 같다.

 

따라서, 맨 위의 $\nu_2$ 식에서 

$$n(n-1) < 2k$$

$\nu_3$ 식에서

$$\frac{k}{3}-1 \leq \nu_3(k!) < \frac{3n}{4}$$

두 식을 잘 연립하면, 

$\frac{3n}{4} > \frac{k}{3}-1 > \frac{n(n-1)}{6}-1$ 이므로, $n$의 범위가 $-2 \leq n \leq 6$ 이다.

 

경우가 몇개 없으므로, 직접 하나씩 확인하면서 답을 찾자. 양의 정수라고 했으므로,

$n = 1$ 인 경우, $k = 1$.

$n = 2$ 인 경우, $k = 3$.

$n = 3$ 인 경우, $k! = 7*6*4$인데, 그런 $k$는 없다.

(이 정도까지는 손으로 해보면 그런 $k$가 없음을 보이기는 어렵지 않다)

 

$n = 4$ 인 경우, $k! = 15 * 14 * 12 * 8$이고, 그런 $k$는 없다. (전부 소인수분해해 보면 어렵지 않다.)

 

$n = 5$ 인 경우, $k! = 31 * 30 * 28 * 24 * 16$ 이고, 그런 $k$는 없다.

(일단 31이 들어가야 하므로 31! 이상인데, 그러면 $k!$ 이 훨씬 크니까)

 

$n = 6$ 인 경우, $k! = 63 * 62 * 60 * 56 * 48 * 32$ 인데, 그런 $k$는 없다.

(일단 62가 들어가야 하므로, $k \geq 31$ 이다. 그러면, 소수인 29가 들어가야 하는데, $k!$의 식에 29가 없으므로 모순.)

 

따라서, 가능한 경우는 단 두 가지로,

$(k. n) = (1, 1), (3, 2)$.

 

---

풀고 나서 AOPS를 보니, 나랑 똑같이 푼 사람도 있고, $\log$함수가 위로 볼록함을 이용하여 바운드를 더 작게 줄인 사람도 있고... 

아무튼 LTE Lemma를 사용하는 풀이 자체는 맞는 것 같다.

 

문제에 대한 평가는 "Easy for Trained students" 던데, 솔직히 국대의 위엄을 느끼게 해주는 멘트였다. 나는 꽤 힘들었기 때문에...

정수론 공부가 재밌어서 해보려고 하긴 하지만, 중학교 때부터 이런 수학을 계속 공부하고 접하면서 살아온 사람들이 새삼 대단하다는 생각이 든다. 그리고 솔직히 그때부터 시작했으면 내가 얼마나 할 수 있었을까 싶은 생각도 조금은 있고.

 

나머지 IMO 문제는 솔직히 1번 외에는 풀수 있을 것 같은 생각이 전혀 안 든다는 것도 그렇고... 이런 문제 푸는게 재밌긴 한데, 갈 길이 너무 멀다 ㅇㅁㅇ