인상 깊었던 MO 문제 #6: China TST 2018 Day 2 2번

문제

주어진 자연수 \(k\)에 대하여, $$ \binom{n}{0}, \quad \binom{n}{1}, \quad \cdots \quad \binom{n}{n-1},  \quad \binom{n}{n}$$ 중 \(0.99n\)개 이상의 자연수가 \(k\)의 배수라면 자연수 \(n\)을 좋은 수라고 하자. 

\(1, 2, \cdots N\) 중 좋은 수의 개수가 \(0.99N\)개 이상인 자연수 \(N\)이 존재함을 보여라.

스포 방지선

_____________________________________________________________________________________________________

______________________________________________________________________________________________________

푸는 것만큼 서술이 참 어려운 문제인 것 같다. 문제를 확장하여, \(0<C, D<1\)에 대하여 다음을 보일 것이다.

[새로운 명제]

주어진 자연수 \(k\)에 대하여, $$ \binom{n}{0}, \quad \binom{n}{1}, \quad \cdots \quad \binom{n}{n-1},  \quad \binom{n}{n}$$ 중 \(Cn\)개 이상의 자연수가 \(k\)의 배수라면 자연수 \(n\)을 \(C\)-좋은 수라고 하자. 

충분히 큰 자연수 \(N\)에 대하여, \(1, 2, \cdots N\) 중 \(C\)-좋은 수의 개수가 \(DN\)개 이상이다. 

\(a_n\)을 \(0 \le v \le u < n\)과 \(\binom{u}{v} \equiv 0 \pmod k\)를 만족하는 정수 순서쌍 \((u,v)\)의 개수라 하자.

\(b_n\)을 \(0 \le v \le u < n\)을 만족하는 정수 순서쌍 \((u,v)\)의 개수, 즉 \(\binom{n+1}{2}\)라 하자.

일단 \(k\)가 prime power인 경우에 대해서 먼저 다룬다. \(k=p^e\)라 하자. 

Claim 1. 모든 양의 실수 \(\epsilon>0\)에 대하여, 적당한 자연수 \(N\)이 존재하여 모든 \(n>N\)에 대해 \(\frac{a_{p^n}}{b_{p^n}} > 1-\epsilon \)가 성립한다. 

Proof of Claim 1. Kummer's Theorem에 의해, \(\binom{u}{v}\)가 가지는 \(p\)의 개수는 \(p\)진법에서 \(v+(u-v)=u\)를 덧셈할 때 발생하는 자리 올림의 횟수가 된다. 이러한 자리올림은 최소한 "\(u\)의 digit이 \(v\)의 digit보다 작은 횟수"만큼 발생한다. 

이제부터 \(u, v\)는 leading zero까지 생각하여 \(p\)진법에서 \(n\)자리 수로 본다. 

이에 기반하여 \(b_{p^n}-a_{p^n}\)을 bound 하자. \(0 \le v \le u < p^n\)를 만족하고 "\(u\)의 digit이 \(v\)의 digit보다 작은 횟수"가 \(e\)번 이하인 정수 순서쌍 \((u,v)\)의 개수를 세면, 이는 \(b_{p^n}-a_{p^n}\)의 upper bound 역할을 할 수 있게 된다. 

\(u\)와 \(v\)가 같은 경우는 \(p^n\)개가 있다. \(u\)와 \(v\)가 다른 경우는 첫 \(s\)개의 digit이 같다고 두고 \(u\)의 \(s+1\)번째 digit이 \(v\)의 \(s+1\)번째 digit보다 크다고 하자. \(s\)에 따라 경우를 나누고, 또 "\(u\)의 digit이 \(v\)의 digit보다 작은 횟수"로 경우를 나누어보자.

우선 첫 \(s\)개의 자리를 결정하는 방법은 최대 \(p^s\)개이고, \(s+1\)번째 digit을 결정하는 방법은 최대 \(\binom{p}{2}\)개이다. 

만약 "\(u\)의 digit이 \(v\)의 digit보다 작은 횟수"가 \(i\)번이라면, \(s+2\)번째부터 \(n\)번째 자리를 결정하는 방법의 수는 최대 $$ \binom{n-s-1}{i} \cdot \binom{p}{2}^i \cdot \binom{p+1}{2}^{n-s-1-i} $$개다. 이를 모두 종합하면, \(b_{p^n}-a_{p^n}\)은 최대 $$ p^n + \sum_{s=0}^{n-1} p^s \binom{p}{2} \sum_{i=0}^e \binom{n-s-1}{i} \cdot \binom{p}{2}^i \cdot \binom{p+1}{2}^{n-s-1-i} $$이다.

\(b_{p^n} \ge \frac{1}{2}p^{2n}\)이므로 이제 목표는 임의의 \(\epsilon>0\)에 대하여, 충분히 큰 \(n\)에 대해서는 저 식이 \(\epsilon \cdot p^{2n}\) 이하임을 보이는 것이다.

시그마 안에 있는 값들부터 천천히 bound하면서, 식 전체에 대한 bound를 잡아보자. 

먼저 간단한 부등식인 \(\binom{n-s-1}{i} \le n^i\), \(\binom{p}{2} \le \binom{p+1}{2}\)을 쓰면, $$ \binom{n-s-1}{i} \cdot \binom{p}{2}^i \cdot \binom{p+1}{2}^{n-s-1-i} < \binom{n-s-1}{i} \cdot \binom{p+1}{2}^{n-s-1} < n^i \cdot p^{2n-2s-2} \cdot \left(\frac{p+1}{2p}\right)^{n-s-1} $$를 얻는다. 그러면 \(b_{p^n}-a_{p^n}\)은 최대 $$ p^n + \sum_{s=0}^{n-1} p^s \binom{p}{2} \cdot p^{2n-2s-2} \cdot \left(\frac{p+1}{2p}\right)^{n-s-1} \cdot \sum_{i=0}^e n^i < p^n + \sum_{s=0}^{n-1} p^{2n-s} \cdot \left(\frac{p+1}{2p}\right)^{n-s-1} \cdot n^{e+1}$$이다. 이제 등비수열의 합에 의하여, $$ \sum_{s=0}^{n-1} p^{2n-s} \cdot \left(\frac{p+1}{2p}\right)^{n-s-1} = \frac{2p}{p+1} \cdot p^{2n} \cdot \left(\frac{p+1}{2p}\right)^n \cdot \sum_{s=0}^{n-1} \left(\frac{p+1}{2}\right)^{-s} < \frac{2p}{p+1} \cdot p^{2n} \cdot \left(\frac{p+1}{2p}\right)^n \cdot \frac{p+1}{p-1}$$이며, 이를 다시 위 식에 대입하고 정리하면 $$b_{p^n}-a_{p^n} \le p^n + n^{e+1} \cdot \frac{2p}{p-1} \cdot \left(\frac{p+1}{2p}\right)^n \cdot p^{2n} $$을 얻는다. \(n\)이 커짐에 따라 \(n^{e+1} \cdot \left(\frac{p+1}{2p}\right)^n\)은 \(0\)으로 수렴하므로, 적당한 \(\epsilon-\delta\) 논법을 끼얹으면 Claim 1의 증명이 끝난다.

Claim 2. 모든 양의 실수 \(\epsilon>0\)에 대하여, 적당한 자연수 \(N\)이 존재하여 모든 \(n>N\)에 대해 \(\frac{a_n}{b_n} > 1-\epsilon \)가 성립한다.

Proof of Claim 2. \(\epsilon>0\)을 고정하자. Claim 1에 의해, \(n>N\)이면 \(\frac{a_{p^n}}{b_{p^n}} > 1-\frac{1}{p^9}\epsilon \)이 성립하는 \(N\)이 존재한다. 

이제 \(n>p^{N+9}\)이라 하자. \(p^L \le n < p^{L+1}\)인 \(L\)을 잡으면 \(L>N\)이다.

정의상 \(b_n-a_n\), \(a_n\), \(b_n\)은 모두 단조증가하는 수열이므로, \(b_n-a_n \le b_{p^{L+1}}-a_{p^{L+1}} \le b_{p^{L+1}} \cdot \frac{1}{p^9} \epsilon \)이다. 

그러므로 \(\frac{a_n}{b_n} = 1-\frac{b_n-a_n}{b_n} \ge 1-\frac{b_{p^{L+1}}}{b_n} \cdot \frac{1}{p^9} \cdot \epsilon \ge 1-\frac{b_{p^{L+1}}}{b_{p^L}} \cdot \frac{1}{p^9} \cdot \epsilon > 1-\epsilon\)이 성립한다. 

Claim 3. \(k=p^e\)인 경우, [새로운 명제]가 참이다. 

Proof of Claim 3. 귀류법으로 [새로운 명제]가 거짓이라고 하자. 

각 \(i\)에 대하여, \(0 \le j \le i\) 중 \(\binom{i}{j}\)가 \(k\)의 배수인 것의 개수를 \(c_i\)라 하고, \(rat_i = \frac{c_i}{i+1}\)이라 하자. \(rat_0=0\)이다.

귀류법 가정에서 임의의 자연수 \(N\)에 대해 \(n>N\)인 \(n\)이 있어 \(1 \le i \le n\) 중 \(rat_i \ge C\)인 것은 최대 \(Dn\)개다.  

이 상황에서 \(a_{n+1} = \sum_{i=1}^{n} rat_i (i+1) \)을 bound해보자. 그렇다면, 다음 두 가지 관찰을 통해 bound를 구할 수 있다. 

관찰 1: \(rat_i\)가 \(C\) 이상이라면, 편하게 \(rat_i\) 대신 \(1\)이라고 두자. \(rat_i\)가 \(C\) 미만이라면, 마찬가지로 \(rat_i\) 대신 \(C\)라고 두자. 

관찰 2: 이제 문제는 \(rat_i\)는 \(C\) 또는 \(1\)이고, \(1\)인 index가 최대 \(Dn\)개다. 이런 구조에서는 재배열 부등식을 사용할 수 있다. 

이 관찰을 통해서, \(a_{n+1}\)의 bound를 구하기 위해 \(C\)를 작은 \(i\)에 몰아주고, \(1\)을 큰 \(i\)에 몰아준다. 계산하면 $$ a_{n+1} \le \sum_{i=1}^{n-\lfloor Dn \rfloor} C(i+1) + \sum_{i=n+1-\lfloor Dn \rfloor}^{n} (i+1)  = b_{n+1} - (1-C) \sum_{i=1}^{n-\lfloor Dn \rfloor} (i+1) \le b_{n+1} - (1-C) \cdot \binom{n+1-\lfloor Dn \rfloor}{2} $$를 얻는다. 하지만 이는 Claim 2에 모순임을 쉽게 알 수 있다. $$ b_{n+1} - a_{n+1} \ge (1-C) \cdot \binom{n+1-\lfloor Dn \rfloor}{2} \sim (1-C)(1-D)^2 \cdot  \frac{n^2}{2} \sim (1-C)(1-D)^2 \cdot b_{n+1}$$이므로, 아주 작은 \(\epsilon\)을 잡고 Claim 2를 쓰면 \(n\)의 upper bound를 얻을 수 있고, 즉 모순을 얻을 수 있기 때문이다. 

Claim 4. \(\text{gcd}(a,b)=1\)인 두 자연수 \(a, b\)에 대해 \(k=a, b\)인 경우 [새로운 명제]가 참이면, \(k=ab\)인 경우에도 참이다. 

Proof of Claim 4. \(C'=\frac{1+C}{2}\), \(D'=\frac{1+D}{2}\)라 하자. \(0<C', D'<1\)이다.

가정에 의해서, \(k=a\)라면 자연수 \(N_1\)이 존재하여, 모든 \(n>N_1\)에 대해 \(0, 1, \cdots n\) 중 \(C'\)-좋은 수가 \(D'n\)개 이상이다. 

가정에 의해서, \(k=b\)라면 자연수 \(N_2\)이 존재하여, 모든 \(n>N_2\)에 대해 \(0, 1, \cdots n\) 중 \(C'\)-좋은 수가 \(D'n\)개 이상이다. 

\(N=\text{max}(N_1, N_2)\)라 하자. 이제 \(n>N\)이라 해보자. 

\(0, 1, \cdots n\) 중 \(k=a\)에 대해 \(C'\)-좋은 수의 집합을 \(G_1\), \(k=b\)에 대해 \(C'\)-좋은 수의 집합을 \(G_2\)라 하자. 

\(|G_1| \ge D'n\), \(|G_2| \ge D'n\)이고 \(|G_1 \cup G_2| \le n\)이므로 \(|G_1 \cap G_2| \ge Dn\)이다. 

한편, \( t \in G_1 \cap G_2\)라 하고 \(\binom{t}{0}, \binom{t}{1}, \cdots , \binom{t}{t}\) 중 \(a\)의 배수의 집합을 \(S_1\), \(b\)의 배수의 집합을 \(S_2\)라 하면 \(|S_1| \ge C'(t+1)\), \(|S_2| \ge C'(t+1)\), \(|S_1 \cup S_2| \le t+1\)이니 \(|S_1 \cap S_2| \ge C(t+1)\)다. 

여기서 \(2C'-1=C\), \(2D'-1=D\)과 \(|A|+|B|=|A \cup B|+|A \cap B|\)를 사용하였다. 

그런데 \(|S_1 \cap S_2|\)는 \(ab\)의 배수의 개수다. 즉, \(t\)는 \(k=ab\)에 대한 \(C\)-좋은 수다. 증명 끝.

이제 Claim 3과 Claim 4에 의해서, 모든 \(k \ge 2\)에 대한 증명이 끝난다. \(k=1\)은 자명하니 증명 끝.