문제 (문제 링크)


\(a, b, c\)가 \(abc=1\)을 만족하는 양의 실수라면, 다음 부등식이 성립함을 보여라. $$ (a+1)^b \cdot (b+1)^c \cdot (c+1)^a \ge 8 $$


스포 방지선

___________________________________________________________________________________________________________














__________________________________________________________________________________________________________


풀이 (2015/10/17 - 3년 반 전에 푼 문제인데 어떻게 풀었는지 모르겠다)


먼저 \(a, b, c\)를 \( \displaystyle \frac{1}{a}, \frac{1}{b}, \frac{1}{c}\)로 바꿔치자. 이렇게 해도 문제가 되지 않는다는 것을 쉽게 알 수 있다.

이제 목표는 \(abc=1\)인 양의 실수 \(a,b,c\)에 대해 \(\displaystyle \left(1+\frac{1}{a}\right)^{1/b} \cdot \left(1+\frac{1}{b} \right)^{1/c} \cdot \left(1+\frac{1}{c} \right)^{1/a} \ge 8\)을 보이는 것이다.

자연로그를 취하면, \(\displaystyle \frac{1}{b} \ln \left(1+\frac{1}{a}\right) + \frac{1}{c} \ln \left(1+\frac{1}{b}\right) + \frac{1}{a} \ln \left(1+\frac{1}{c} \right) \ge 3 \ln 2\)를 보이면 충분하다.


한편, 모든 \(x > 0\)에 대하여 \(\displaystyle \ln \left(1+\frac{1}{x} \right) = \ln (x+1) - \ln (x) = \int_x^{x+1} \frac{1}{t} dt = \int_0^1 \frac{1}{x+t} dt \)이므로, 이제 $$ \int_0^1 \left( \frac{1}{b} \cdot \frac{1}{a+t} + \frac{1}{c}  \cdot \frac{1}{b+t} + \frac{1}{a} \cdot \frac{1}{c+t} \right) dt \ge 3 \ln 2 $$를 보이면 충분하다.


이제 \(abc=1\)이므로, 양의 실수 \(x,y,z\)에 대해 \(\displaystyle a=\frac{x}{y}, b=\frac{y}{z}, c=\frac{z}{x}\)라 쓸 수 있다. 대입하면 우리는 $$ \int_0^1 \left( \frac{z}{yt+x} + \frac{x}{zt+y} + \frac{y}{xt+z} \right) \ge 3\ln2$$를 보이면 충분하다. 한편, 전형적인 Cauchy-Schwarz 부등식에 의해서 $$ \frac{z}{yt+x} + \frac{x}{zt+y} + \frac{y}{xt+z} = \frac{z^2}{yzt+zx} + \frac{x^2}{zxt+xy} + \frac{y^2}{xyt+yz} \ge \frac{(x+y+z)^2}{(xy+yz+zx)(t+1)} $$이므로, 두 함수 \(f(t), g(t)\)가 \(f(t) \ge g(t) \text{ } \forall t \in [0,1]\)를 만족하면 \(\displaystyle \int_0^1 f(t) dt \ge \int_0^1 g(t) dt\)가 성립한다는 사실에서 $$ \int_0^1 \left( \frac{z}{yt+x} + \frac{x}{zt+y} + \frac{y}{xt+z} \right) dt \ge \int_0^1 \frac{(x+y+z)^2}{(xy+yz+zx)(t+1)} dt \ge \int_0^1 \frac{3}{t+1} dt = 3 \ln 2 $$를 얻을 수 있다. 여기에서는 \((x+y+z)^2 \ge 3(xy+yz+zx)\)라는 잘 알려진 부등식을 사용하였다.

등호가 성립하려면 \((x+y+z)^2=3(xy+yz+zx)\)이어야 하고, 이는 \(x=y=z\), 즉 \(a=b=c=1\)을 뜻한다.


문제


주어진 자연수 \(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\)은 자명하니 증명 끝. 



문제


자연수 \(n\)에 대하여, \(\mathbb{Z}/n\mathbb{Z}\)는 정수의 집합을 modulo \(n\)으로 본 것이다. 

다음을 만족하는 함수 \(g: \mathbb{Z}/n\mathbb{Z} \rightarrow \mathbb{Z}/n\mathbb{Z}\)가 존재하는 자연수 \(n\)을 모두 구하시오. $$ g(x), \quad g(x) + x, \quad g(x) + 2x, \quad \dots, \quad g(x) + 100x $$가 모두 \(\mathbb{Z}/n\mathbb{Z}\)위의 일대일대응 함수이다. 


스포 방지선

_________________________________________________________________________________________________________
















___________________________________________________________________________________________________________

답은 \(101!\)과 서로소인 모든 자연수들이다. \(\text{gcd}(n,101!)=1\)이라면 \(g(x)=x\)가 조건을 만족한다.

이제 \(\text{gcd}(n,101!)\neq1\)이라고 생각하자. \(n\)의 최소 소인수를 \(p\)라 하면, \(p \le 101\)이다.


각 \(0 \le k \le p-1\)에 대해서, \(k \le p-1 \le 100\)임을 상기하면 $$ \sum_{x} g(x)^k \equiv \sum_{x} (g(x)+x)^k \equiv \sum_{x} (g(x)+2x)^k \equiv \cdots \equiv \sum_{x}(g(x)+kx)^k \equiv \sum_{i=0}^{n-1} i^k \pmod{n}$$이다. 각 식에서 더하고 있는 term들에 대한 \(k\)차 차분을 취하면,  $$ \sum_{x} k!x^k \equiv 0 \pmod{n}$$을 얻는다. 한편, \(p\)는 \(n\)의 최소 소인수이므로 \(\text{gcd}(k!,n)=1\)이다. 그러니 $$ \sum_{x} x^k \equiv 0 \pmod{n}$$을 얻는다. 그러므로 $$ 0 \equiv \sum_{x=1}^n (x-1)\cdots (x-(p-1)) \equiv (p-1)! \sum_{x=1}^n \binom{x-1}{p-1} \equiv (p-1)! \binom{n}{p} \pmod{n} $$를 얻을 수 있고, 이는 \(n| \binom{n}{p}\)를 얻는다. 이는 \(p \nmid n\)을 강제하고, 모순이다. 

문제


\(K\)는 십진법 표현에서 \(7\)을 포함하지 않는 자연수의 집합이다. 

다음 조건을 만족하는 모든 계수가 음이 아닌 정수인 다항식 \(f\)를 모두 찾아라. $$ n \in K \implies f(n) \in K $$

스포 방지선

________________________________________________________________________________________________________
















_________________________________________________________________________________________________________


꽤 재밌는 문제다. 먼저 문제를 단항식으로 압축해준다.


Claim: \(f(x) = \sum_{i=0}^n a_i x^i\)가 조건을 만족하면, 각각의 \(a_i x^i\)도 조건을 만족한다.

증명은 간단하다. 모든 \(x \in K\)에 대해 \(\sum_{i=0}^n a_i x^i \in K\)라면, 모든 자연수 \(N\)에 대하여 \(\sum_{i=0}^n a_i (10^Nx)^i  = \sum_{i=0}^n a_ix^i \cdot 10^{Ni} \in K\)이다. 이는 \(10^Nx \in K\)이기 때문.

\(N\)을 매우 크게 잡으면 \(a_ix^i\)가 그대로 십진법 표현에 나오고, 결국 \(x \in K \implies a_i x^i \in K\)를 얻는다.  


이제 단항식을 보자. 먼저 1차식에 대한 논의를 진행한다.


Claim: \(f(x)=cx\)가 조건을 만족한다면, \(c\)는 \(10^e\) 형태로 쓸 수 있는 자연수다. 

\(c \neq 10^e\)라면, 적당한 \(x \in K\)가 있어서 \(cx \not\in K\)임을 보이면 된다. 

실제로는 \(cx\)의 첫 번째 자릿수가 \(7\)이 되도록 할 수 있다. \(c\)의 범위를 세세하게 나누고, 각 경우에서 \(x\)를 대응시켜주자. 


이제 2차 이상의 단항식을 보자. 모두 불가능함을 보여주자.


Claim: \(f(x)=cx^k\)는 \(k \ge 2\)라면 조건을 만족할 수 없다.

\(x \in K\)를 잡고 \(f(10x+3)\)을 생각하자. \(10x+3 \in K\)이므로, $$f(10x+3)=c(10x+3)^k = c \cdot 3^k + c \cdot 10 \cdot k \cdot 3^{k-1} x + \cdots $$는 \(K\)에 속한다. 앞선 Claim에서 \(10ck3^{k-1}x\)는 조건을 만족시키는 단항식이고, 이는 위 Claim에 의해 \(10ck3^{k-1}\)이 \(10^e\) 형태의 자연수임을 의미한다. 하지만 \(k \ge 2\)면 \(10ck3^{k-1} \equiv 0 \pmod{3}\)이므로 이는 불가능하다. 


결국 답은 \(f(x)=10^e x\), \(f(x)=k\) (단, \(k \in K\)), \(f(x)=10^ex + k\) (단, \(10^e > k, k \in K\)) 뿐임을 알 수 있다. 



문제

임의의 주어진 양의 실수 \(\epsilon\)에 대하여, 모든 충분히 큰 \(v\)에 대하여 다음이 성립함을 보여라.

\(v\)개의 정점을 가진 그래프가 \((1+\epsilon)v\)개 이상의 간선을 가진다면, 같은 길이를 가지는 두 distinct simple cycle을 갖는다.  



스포 방지선

__________________________________________________________________________________________________________















___________________________________________________________________________________________________________


아는 풀이만 3개다. 각자 다른 맛을 가지고 있으니 다 읽어보자.


풀이 1. (Probabilistic)

서로 다른 simple cycle of equal length가 없는 그래프에 대해서 \(|E|\)를 bound시키면 된다. 

간선들의 집합 \(B\)를 뽑았다고 가정하고, \(B\)에 속한 간선들을 삭제하자. 만약 남은 cycle의 개수가 \(f(B)\)개라면, \(|B|+f(B)\)개의 간선을 삭제하여 cycle-free 그래프를 만들 수 있고, 그러면 \(|E| \le |V|+|B|+f(B)\)를 얻는다. 

문제는 적당한 \(B\)를 뽑는 것이다. Probabilistic한 방법이 이런 경우에 도움이 될 수 있다. 

\(B\)를 뽑기 위해서, 각 간선이 추가될 확률을 \(\frac{1}{\sqrt{|E|}}\)로 고정하자. 각 간선의 선택 여부는 독립적이다.

기댓값의 선형성에 의해 \(E\left(|B|+f(B)\right) = E(|B|)+E(f(B))\)이다. \(E(|B|)=\sqrt{|E|}\)는 자명하다. 

각 cycle이 \(B\)에서 속한 간선을 모두 제거했을 때에도 살아남은 조건은 그 cycle에 속한 모든 간선이 \(B^C\)에 속할 경우이다. 

각 길이를 가지는 cycle은 최대 하나이므로, 결국 \(\displaystyle E(f(B)) \le \sum_{k=3}^\infty \left(1-\frac{1}{\sqrt{|E|}} \right)^k \le \sqrt{|E|}-1\)이다. 

종합하면 \(E \left(|B|+f(B)\right) \le 2\sqrt{|E|}-1\)이다. 그러니 \(|B|+f(B) \le 2\sqrt{|E|}-1\)인 집합 \(B\)가 있다.

이 \(B\)를 통해서, \(|E| \le |V|+2\sqrt{|E|}-1\)를 얻을 수 있고 정리하면 \(|E| \le |V|+2\sqrt{|V|}+1\)를 얻는다.

이제 증명을 마무리시키는 것은 어렵지 않다. 증명 끝. 


풀이 2. (Algorithmic #1)

이 풀이에서는 \(f(B)=0\)을 만족하는 크기가 작은 \(B\)를 더욱 explicit하게 construct한다. 

먼저, 주어진 그래프에서는 최소 \(|E|-|V|\)개의 cycle이 존재하고, 그 길이는 서로 다르므로 \(|E|-|V| \le |V|\)다.

이제 \(B\)를 greedy하게 construct하자. 각 간선 중 가장 많은 cycle에 존재하는 간선을 하나 선택하고, 그 간선을 삭제하는 것을 반복한다. 이 알고리즘이 최대 \(10\sqrt{|V|}\)번의 삭제를 함을 보이자. 즉, \(|B| \le 10\sqrt{|V|}\)를 보이자.

현재 \(x\)개의 cycle이 있다면, 그 길이의 합은 최소 \(\sum_{i=1}^x (i+2) > \frac{1}{2}x^2\)이다.

그러므로, 더블카운팅 느낌으로 생각하면 \(\frac{x^2}{2|E|} \ge \frac{x^2}{4|V|}\)개 이상의 cycle에 존재하는 간선이 있다. 

즉, 한 번 간선을 삭제할 때마다 최소 \(\text{min}(\frac{x^2}{4|V|},1)\)개의 cycle이 삭제된다. 물론 처음에 \(x \le |V|\)이다. 

이제 이 문제는 대수문제다. 알고리즘을 진행하면서, cycle의 개수가 \([k\sqrt{|V|}, (k+1)\sqrt{|V|})\)에 속한 횟수를 \(c_k\)라 하자. 

\(k \ge 1\)이면 \(c_k \le \frac{\sqrt{|V|}}{k^2/4}+1 = \frac{4 \sqrt{|V|}}{k^2}+1\)이고, \(c_0 \le \sqrt{|V|}+1\)이다. (cycle의 개수가 최소 \(\frac{k^2}{4}\) 또는 1개씩 감소)

가능한 \(k\)의 범위는 \(1 \le k \le \lfloor \sqrt{|V|} \rfloor\)이므로, 전체 삭제 횟수는 $$ -1+\sum_{k=0}^{\lfloor \sqrt{|V|}\rfloor} c_k  \le \sqrt{|V|} + \sum_{k=1}^{\lfloor \sqrt{|V|} \rfloor} \left( \frac{4\sqrt{|V|}}{k^2} + 1 \right) \le 2\sqrt{|V|} + 4 \sum_{k=1}^\infty \frac{\sqrt{|V|}}{k^2} \le 10 \sqrt{|V|} $$다. 이제 풀이 1과 똑같은 방법으로 마무리할 수 있다. 증명 끝.


풀이 3. (Algorithmic #2)

접근 방법이 많이 다른 풀이다. 앞서 cycle의 길이가 최대 \(|V|\)인 것을 활용하여 \(|E|-|V| \le |V|\)임을 유도했다. 

만약 그래프의 일부 간선을 삭제하여 diameter가 작은 그래프 여러 개로 분할하면, 그 그래프들에서 나올 수 있는 cycle의 길이는 더욱 tight하게 bound된다. 특정 길이를 가지는 cycle이 최대 하나이므로, 여기서 쪼개진 그래프들이 가질 수 있는 간선의 개수를 bound시킬 수 있을 것이다. 문제는 어떻게 적은 수의 간선을 제거해 diameter가 작은 그래프를 만드냐는 것이다. 


Theorem. (Low Diameter Decomposition) 

\(N\)개의 정점과 \(M\)개의 간선을 가지는 그래프 \(G\)가 있다고 가정하자. 

\(\delta M\)개의 간선을 삭제하여, 남은 connected component의 diameter가 전부 \(\mathcal{O}(\delta^{-1} \log N)\)이도록 할 수 있다. 


(증명) 다음 알고리즘을 반복한다. 

정점 \(v\)를 고정하고, \(B_r\)을 \(\text{dist}_G(v,w) \le r\)인 정점 \(w\)의 집합이라 한다.

또한, \(E(B_r)\)을 \(B_r\) 내부에 존재하는 간선의 개수라고 정의한다. 

\(E(B_r) \le (1+\delta)E(B_{r-1})\)을 만족하는 최소의 \(r\)을 선택한다. 

만약 모든 \(1 \le t \le R\)에 대하여 \(E(B_t) > (1+\delta)E(B_{t-1})\)이 성립한다면, $$ M \ge E(B_R) > (1+\delta)^{R-1} E(B_1) \ge (1+\delta)^{R-1} $$이므로 \(R \le 1+\frac{\log M}{\log (1+\delta)}\)이다. 즉, 최소의 \(r\)은 최대 \(1+\frac{\log M}{\log (1+\delta)} = \mathcal{O}(\delta^{-1} \log N)\)이다. 

이제 \(E(B_r)-E(B_{r-1})\)개의 간선을 삭제하여 \(B_{r-1}\)을 새로운 connected component로 받아들인다.

이를 계속해서 반복한다. 각 stage에서 삭제되는 간선은 최대 \(\delta E(B_{r-1})\)개이다. 

\(B_{r-1}\)은 서로 disjoint한 집합들이므로, 이들의 합은 최대 \(\delta M\)이다. 증명 끝. 


적당히 작은 \(\epsilon\)에 대해서만 생각해도 좋다. 

\(\delta = \frac{\epsilon}{2}\)라 하고 위 알고리즘을 적용하자. 삭제된 간선은 최대 \( \frac{\epsilon}{2} (1+\epsilon)v < \frac{2}{3} \epsilon v\)개다. 

그 후, 각 connected component의 spanning tree를 하나씩 잡아주자. 

그러면 삭제되지도 않았고, spanning tree에도 포함되지 않은 간선은 최소 \(\frac{1}{3}\epsilon v\)개다.

이러한 간선들은 해당 connected component에서 cycle을 만들어주며, 그 길이는 최대 \(\mathcal{O}(\epsilon^{-1} \log v)\)이다. 

cycle의 개수는 최소 \(\frac{1}{3}\epsilon v\)개다. \(\frac{1}{3} \epsilon v >> \epsilon^{-1} \log v\)라면, 비둘기집의 원리에서 같은 길이를 가진 cycle이 생긴다. 

\(v\)가 충분히 큰 값을 가지면, 위 부등식이 성립하게 된다. 증명 끝. 이 방식은 \(v+\mathcal{O}(\sqrt{v \log v})\) 정도의 bound를 준다.


cf. 참고로 풀이 1, 2에서 얻은 \(v+\mathcal{O}(\sqrt{v})\)의 bound는 tight하다. 

길이가 \(3,4, \cdots n\)인 cycle을 준비한 뒤, 하나의 chain으로 붙여주면 된다. 





 



문제

다음 식을 만족하는 non-constant 다항식 \(P(x), Q(x)\)가 존재하는지 판별하시오.


$$ P(x)^{10}+P(x)^9 = Q(x)^{21}+Q(x)^{20} $$


스포 방지선

________________________________________________________________________________________________________________________
















________________________________________________________________________________________________________________________


이 문제도 얘들이 많이 못 풀었는데, 내가 시험장에서 깔끔하게 푼 문제다. 여기서도 점수 좀 딴 듯 ㅋㅋ


(증명) 불가능하다. 귀류법으로 보이자. 조건을 만족하는 non-constant 다항식 \(P, Q\)가 존재한다 가정하자.

다항식 \(f\)에 대하여 \(S_f\)를 \(f(x) = 0\)의 (복소수) 해집합이라 하자. 중근은 한 번만 센다. 다음 관찰을 하자.


관찰 1. \(S_{P} \cap S_{P+1} = S_{Q} \cap S_{Q+1} = \emptyset\)이고, \(S_P \cup S_{P+1} = S_{Q} \cup S_{Q+1} \)이다.

관찰 2. 주어진 식 양변의 차수를 비교하면, \(\text{deg}(P)=21x , \text{deg}(Q)=10x\)인 자연수 \(x\)가 있음을 알 수 있다.  

관찰 3. \(|S_{f}| \le \text{deg} (f)\)가 성립한다. 그러므로 \( |S_P| + |S_{P+1}| = |S_Q|+|S_{Q+1}| \le 20x \)다.


이제 여기서 다음 Lemma를 보이자. 


Lemma. non-constant 다항식 \(f\)에 대하여, \(|S_f| + |S_{f+1}| \ge \text{deg}(f) +1 \)가 성립한다. 


Proof of Lemma. 우선 \( \displaystyle f(x) = \prod_{i=1}^n (x-r_i)^{c_i} \), \( \displaystyle f(x)+1 = \prod_{i=1}^m (x-r'_i)^{c'_i}\)라 하자.

여기서 \(n=|S_f|\), \(m=|S_{f+1}|\)이다. \(r_i, r'_i\)들은 앞선 관찰 1에 의해 모두 서로 다른 복소수다.

한편, \(f'(x)\)는 \(r_i\)를 \(c_i-1\)-중근으로 가지고, \(r'_i\)를 \(c'_i-1\)-중근으로 가진다. 그러므로

$$ \text{deg}(f)-1 =\text{deg}(f')  \ge \sum_{i=1}^n (c_i-1) + \sum_{i=1}^m (c'_i-1) = 2 \text{deg}(f)-n-m$$

가 성립하고, 정리하면 \( |S_f|+ |S_{f+1}| \ge \text{deg}(f)+1\)을 얻는다. \(\blacksquare\)


Lemma와 관찰 3으로 \(20x \ge |S_Q|+|S_{Q+1}| = |S_P|+|S_{P+1}| \ge \text{deg}(P)+1 = 21x+1\)을 얻고, 이는 모순. \(\blacksquare\)


 




문제

\( a_1, a_2, \cdots a_n \)은 \( a_1 a_2 \cdots a_n = 1 \)과 \( 0<a_1 \le a_2 \cdots \le a_n \)을 만족하는 실수들이다.

각 \( 1 \le k \le n \)에 대하여, \( b_k = 2^k (1+a^{2^k}_k) \)라고 정의하자. 이때 다음 부등식이 성립함을 보여라.

$$ \sum_{i=1}^n \frac{1}{b_i} \ge \frac{1}{2} - \frac{1}{2^{n+1}} $$


스포 방지선

_______________________________________________________________________________________________________________________
























________________________________________________________________________________________________________________________


많은 학생들이 삽질을 했고, 일부가 아주 복잡한 테크닉을 활용해서 힘겹게 푼 문제다. 준-보스 문제.

나는 이 문제를 당시에 아주 깔끔하게 풀었는데, 지금 생각해보면 이거 덕분에 점수를 좀 딴 것 같다.


(증명) 일단 다음 Lemma를 먼저 증명한다. 


(Lemma) \( x, y \)는 \( 0< x \le 1, y>0 \)을 만족하는 실수들이다. 이때 다음 부등식이 성립한다.

$$ \frac{1}{2(1+x)} + \frac{1}{4(1+y)} \ge \frac{1}{4} + \frac{1}{4(1+x^2y)} $$


(Proof of Lemma) 항을 적당히 묶어주면서 계산하자. 

$$ \frac{1}{2(1+x)} + \frac{1}{4(1+y)} \ge \frac{1}{4} + \frac{1}{4(1+x^2y)} $$

$$ \iff \frac{1}{2(1+x)} - \frac{1}{4} \ge \frac{1}{4(1+x^2y)} - \frac{1}{4(1+y)} $$

$$ \iff \frac{1-x}{1+x} \ge \frac{(1-x^2)y}{(1+y)(1+x^2y)} \iff (1+y)(1+x^2y) \ge (1+x)^2y$$

$$ \iff 1+x^2y + y+x^2y^2 \ge y+2xy+x^2y \iff (xy-1)^2 \ge 0$$


등호 성립은 보다시피 \( x=1 \) 또는 \( xy=1 \)에서 이루어진다. 


본 문제로 돌아오자. \(n \)에 대한 귀납법으로 문제를 해결한다. \( n=1 \)은 자명.

\( n=2 \)인 경우는 Lemma에 \( x=a^2_1, y=a^4_2 \)를 넣어주면 바로 성립함을 확인할 수 있다.

이때, 등호 성립 조건은 Lemma와 문제에서 주어진 조건에 의해 \( a_1 = a_2 = 1 \)이다. 


이제 귀납법을 적용해보자. 엄밀한 귀납 서술은 생략한다. 


\( a_1 a_2 \cdots a_n = 1 \)과 \( 0<a_1 \le a_2 \cdots \le a_n \)를 만족하는 \( a_1, a_2, \cdots a_n \)를 잡자. 

이제, \( c_1=a^2_1a^2_2 \), \(c_2=a^2_3 \), \(c_3 = a^2_4 , \cdots ,c_{n-1} = a^2_n \)로 새로운 변수를 두자.


Fact. \( 0<c_1 \le c_2 \le \cdots \le c_{n-1} \)이고, \( c_1c_2 \cdots c_{n-1} = 1 \)이다. 


첫 번째 사실은 \( a_1 \le 1\)과 \(a_i \le a_{i+1} \)에서 자명하고, 두 번째 사실은 자명하다.


즉, \( c_i\)들을 가지고 (\(n\)이 하나 줄었으니) 귀납 가정을 사용할 수 있다. 여기서 우리는 

$$ \frac{1}{2(1+a^4_1a^4_2)} + \frac{1}{4(1+a^8_3)} + \cdots \frac{1}{2^{n-1}(1+a^{2^n}_n)} = \sum_{k=1}^{n-1} \frac{1}{2^k(1+c^{2^k}_k)} \ge \frac{1}{2}-\frac{1}{2^n} $$를 얻는다. 이제 \( x= a^2_1, y=a^4_2 \)에 대하여 Lemma를 적용시켜주면, 


$$ \sum_{i=1}^n \frac{1}{b_i} = \frac{1}{2(1+a^2_1)} + \frac{1}{4(1+a^4_2)} + \sum_{k=3}^n \frac{1}{2^k(1+a^{2^k}_k)} $$

$$ \ge \frac{1}{4} + \frac{1}{4(1+a^4_1a^4_2)} + \sum_{k=3}^n \frac{1}{2^k(1+a^{2^k}_k)} \ge \frac{1}{4} + \frac{1}{2} \left( \frac{1}{2} - \frac{1}{2^n} \right) = \frac{1}{2} - \frac{1}{2^{n+1}} $$


등호 성립 조건은 \( a_1 = a_2 = \cdots a_n = 1 \)인 경우이고, 이 경우 밖에 없음을 귀납적으로 보일 수 있다.

스케치만 하자면, \( (a_1, a_2, \cdots a_n) \)에서 등호가 성립하면 \( (a^2_1a^2_2, a^2_3, \cdots a^2_n) \)에서도 등호가 성립하고, 귀납적으로 \( a_1a_2=a_3= \cdots = a_n=1 \)임을 알 수 있다. 이제 Lemma에서의 등호 성립 조건에 의하여 \( a_1=a_2=1 \)를 얻는다. 

초기 조건은 (\(n=1,2\)) 앞에서 했으니 증명이 끝난다. 이에 이 문제에 대한 증명이 끝난다. \( \blacksquare \)