rkm0959

문제 (문제 링크)

\(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\)이 존재함을 보여라.

스포 방지선

_____________________________________________________________________________________________________

______________________________________________________________________________________________________

문제

자연수 \(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 \)