인상 깊었던 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$은 자명하니 증명 끝.