rkm0959

github.com/rkm0959/rkm0959_implements/tree/main/Chebyshev%20Acceleration

매우 최근에 올라온 Acceleration에 대한 Survey Paper arxiv.org/abs/2101.09545을 읽는다. 이 글은 2장을 정리한다.

일단은 관심가는 부분만 읽을 예정인데, 아마 3장을 제일 마지막에 읽을 것 같다. 사전지식이 부족한 경우 이 자료 참고.

Acceleration Survey Paper + OSPEP + Proximal Algorithms Survey Paper 이렇게 읽으면 지식이 좀 쌓이지 않을까 생각중이다..

모든 정리의 번호는 Survey Paper와 같은 번호를 사용한다. 단순히 정리 블로그니까 논문 표현을 그대로 가져다 쓰는 일도 많을 것이다.

이 글에서는 unconstrained quadratic minimization 문제, 즉 $f(x) = \frac{1}{2} x^T Hx - b^Tx$를 최소화하는 문제를 다룬다. 물론 $H$는 symmetric.

이 문제의 optimal point는 $x^{*} = H^{-1}b$임이 자명하다. 즉, 이 문제는 결국 linear system의 해를 빠르게 구하는 문제와 같다.

보통 이러한 minimization 문제를 만나면, 많은 사람들이 Gradient Descent를 생각할 것이다. 

즉, initial point $x_0$와 step-size $\gamma$를 잡고, $x_{i+1} = x_i - \gamma \nabla f(x_i)$를 반복하는 것이다.

이 식을 정리하면 $x_{i+1} = (I - \gamma H) x_i + \gamma b$를 얻고, $x^{*}$의 식을 이용하면 $$x_{k+1} - x^{*} = (I - \gamma H) (x_k - x^{*})$$를 얻는다. 이제 우리의 목표는 $I - \gamma H$의 matrix norm을 최소화하는 것이다. 우리는 일반적으로 2-norm, 즉 Spectral Norm을 생각한다.

이제 잠시 $H$로 가능한 행렬의 범위를 좁혀, 적당한 $\mu, L > 0$에 대해 $\mu I \le H \le L I$가 성립한다고 가정하자.

그러면 우리는 $\gamma$를 선택하는 과정에서 worst-case convergence를 최선으로 하기 위해서 $$\max_{\mu I \le H \le LI} ||I - \gamma H||_2$$를 최소화할 필요가 있다. 이 문제는 결국 $\text{max}(|1-\mu \gamma|, |L \gamma - 1|)$를 최소화하는 것이다. 그러니 $\displaystyle \gamma = \frac{2}{\mu + L}$를 잡을 수 있다.

특히 이 경우 $\displaystyle ||I - \gamma H||_2 \le \frac{L - \mu}{L + \mu} = \frac{\kappa - 1}{\kappa + 1}$이고 ($\kappa = L / \mu$는 condition number) $$||x_k - x^{*}||_2 \le \left( \frac{\kappa - 1}{\kappa + 1} \right)^{k} ||x_0 - x^{*}||_2$$를 얻는다. 이것이 Gradient Descent의 수렴 속도가 되겠다. 이를 더 빠르게 하는 것이 우리의 목표다.

이번에는 조금 더 넓은 class의 알고리즘을 생각해보자. $x_{k+1}$을 $x_k$에 $\nabla f(x_k)$의 상수배를 더한 것만 고려하지 말고, 아예 $$x_{k+1} \in x_0 + \text{span} \{ \nabla f(x_0), \cdots , \nabla f(x_k) \}$$를 고려하자. 이 경우, 단순한 수학적 귀납법으로 다음을 보일 수 있다.

Proposition 2.1. : 위와 같은 방식으로 $x_k$를 계산한 경우, 다항식 $P_k$가 있어 $\text{deg}(P_k) \le k$, $P_k(0) = 1$이고 $$x_k - x^{*} = P_k(H)(x_0 - x^{*})$$ 이제 우리는 앞선 사고방식을 그대로 따라가면 $$\displaystyle \max_{\mu I \le H \le LI} ||P_k(H)||_2$$를 최소화하고 상수항이 $1$인 $k$차 이하 다항식 $P_k$를 찾아야 한다. 그런데 $H$가 symmetric이므로, 이 문제는 사실 $$\max_{\mu \le \lambda \le L} |P_k(\lambda)|$$를 최소화하는 것과 같다. 이제 짬이 좀 찬 독자들은 Chebyshev라는 단어가 왜 나왔는지 알 것이다. 저런 문제에서 최적의 다항식이 Chebyshev Polynomial이기 때문이다. 이들은 $[-1, 1]$ 위에서 최적이기 때문에, $[\mu, L]$을 $[-1, 1]$로 shift 하는 처리 작업이 필요하다. 즉, $$t : x \rightarrow \frac{2x - (L + \mu)}{L - \mu}$$의 처리를 하자. 또한, $P_k(0)=1$이라는 조건이 있으니 이것도 처리해야 한다. 결과적으로 우리는 $$C_k^{[\mu, L]}(x) = \frac{T_k(t(x))}{T_k(t(0))}$$라는 다항식을 정의할 수 있다. 이제 목표는 $$x_k - x^{*} = C_k^{[\mu, L]}(H) (x_0 - x^{*})$$가 성립하도록 효율적인 iteration을 설계하는 것이다. 이를 위해서는 $C_k^{[\mu, L]}$에 대한 점화식이 필수적이다. 결과적으로, $$\delta_0 = -1, \quad \delta_k = \frac{L - \mu}{2(L + \mu) - \delta_{k-1}(L - \mu)}$$ $$C_0^{[\mu, L]}(x) = 1, \quad C_1^{[\mu, L]}(x) = 1 - \frac{2}{L + \mu}x, \quad C_k^{[\mu, L]}(x) = \frac{2\delta_k (L+\mu - 2x)}{L - \mu} C_{k-1}^{[\mu, L]}(x) + \left( 1 - \frac{2\delta_k (L+\mu)}{L - \mu} \right) C_{k-2}^{[\mu, L]}(x)$$가 성립함을 보일 수 있다. Chebyshev Polynomial의 점화식을 가지고 열심히 계산하면 될 것으로 예상한다.

이제 이를 $x_k - x^{*} = C_k^{[\mu, H]}(x_0 - x^{*})$에 집어넣고 $\nabla f(x_k) = Hx_k - b = H(x_k - x^{*})$를 이용하면, iteration $$x_k = \frac{2\delta_k}{L-\mu} ((L+\mu) x_{k-1} - 2 \nabla f(x_{k-1})) + \left( 1 - \frac{2\delta_k (L + \mu)}{L - \mu} \right) x_{k-2}$$를 얻는다. 이 iteration에 대해서 몇 가지 고찰을 해보자. 이 식은 $$x_k = x_{k-1} - \frac{4 \delta_k}{L - \mu} \nabla f(x_{k-1}) + \left( 1  - \frac{2\delta_k (L+\mu)}{L - \mu} \right)(x_{k-2} - x_{k-1})$$이라 쓸 수 있다. 결국 Gradient Descent Term (step size는 변화함) + Momentum Term (변화함) 으로 볼 수 있다.

특히, $\delta_k$의 극한을 취하면 $\displaystyle \frac{\sqrt{L}-\sqrt{\mu}}{\sqrt{L} + \sqrt{\mu}}$로 수렴함을 알 수 있으며, 이 값을 iteration에 그대로 대입하면 Heavy Ball Method를 얻는다고 한다.

이제 이 새로운 iteration의 수렴 속도를 알아보자. 결국 $\lambda \in [\mu, L]$에 대하여 $$|C_k^{[\mu, L]}(\lambda)| \le \frac{1}{|T_k(t(0))|}$$이 성립하고, 여기서 $\displaystyle \xi = \frac{\sqrt{\kappa}+ 1}{\sqrt{\kappa} - 1}$라 하면 위 식의 우변이 정확하게 $\displaystyle \frac{2}{\xi^k + \xi^{-k}}$와 같음을 알 수 있다. 그러니 이를 그대로 대입하여 $$||x_k - x^{*} ||_2 \le \frac{2}{\xi^k + \xi^{-k}} ||x_0 - x^{*}||_2$$를 얻는다. 이제 이를 기존의 Gradient Descent와 비교할 일만 남았다. 이를 위해서는 원하는 정확도를 위해서 iteration이 얼마나 필요한지 보면 된다.

Corollary 2.2. : 고정된 $\mu, L$에 대하여, $||x_k - x^{*}||_2 \le \epsilon$을 얻기 위하여 필요한 $k$의 값은

• 기존 Gradient Descent의 경우 $\displaystyle k \ge 2 \kappa  \log (||x_0-x^{*}||_2 / \epsilon)$
• 새로운 Chebyshev Method의 경우 $\displaystyle k \ge 2 \sqrt{\kappa} \log(2 ||x_0-x^{*}||_2 / \epsilon)$

그러니 Chebyshev Method의 강력함을 알 수 있다. 특히 $\kappa$가 큰 경우 더욱 강력한 힘을 발휘한다.

Ramsey Number는 이산수학에서 중요하게 다뤄지는 주제 중 하나다. 

Ramsey Number \(R(n, m)\)는 정점이 \(V\)개인 완전그래프 \(G\)의 간선을 빨간색/파란색 중 하나로 색칠할 때, 빨간색 간선으로만 이루어진 완전그래프 \(K_n\) 또는 파란색 간선으로만 이루어진 완전그래프 \(K_m\)이 존재하게 되는 \(V\)의 최솟값으로 정의된다. 

이를 확장해서, 그래프 \(G_1, G_2\)에 대해 \(R(G_1, G_2)\)를 정점이 \(V\)개인 완전그래프 \(G\)의 간선을 빨간색/파란색 중 하나로 색칠할 때, 빨간색 간선으로만 이루어진 \(G_1\) 또는 파란색 간선으로만 이루어진 \(G_2\)가 존재하게 되는 \(V\)의 최솟값으로 정의하자.

본 포스팅에서는 1977년에 증명된 다음 정리를 증명한다. 

Theorem: (V. Chvatal) 

임의의 정점 \(n\)개를 가진 트리 \(T_n\)과 완전그래프 \(K_m\)에 대해서, \(R(T_n, K_m) = (n-1)(m-1)+1\)이 성립한다.

Theorem 증명

이제부터 빨간색 간선만 간선으로 본다. 즉, 이제부터 \(G\)는 빨간색 간선으로만 이루어진 그래프다. 

마찬가지로, \(\overline{G}\)는 파란색 간선으로만 이루어진 그래프다. 먼저 \(R(T_n, K_m) \ge (n-1)(m-1)+1\)을 보인다.

\(K_{n-1}\)을 \(m-1\)개 깔아놓은 것을 \(G\)라 하면, \(G\)는 \(T_n\)을 포함하지 않고 \(\overline{G}\)는 \(K_m\)을 포함하지 않는다. 

그러니 \(R(T_n, K_m) > |V(G)| = (n-1)(m-1)\)이 되고 \(R(T_n, K_m) \ge (n-1)(m-1)+1\)을 얻는다.

이제 \(R(T_n, K_m) \le (n-1)(m-1)+1\)이 성립함을 증명하자.

즉, \((n-1)(m-1)+1\)개의 정점을 가진 그래프 \(G\)가 있다면, \(G\)가 \(T_n\)을 포함하거나 \(\overline{G}\)가 \(K_m\)을 포함함을 증명하자. 

\(\overline{G}\)가 \(K_m\)을 포함하지 않으면, \(G\)가 \(T_n\)을 포함함을 보이면 된다. 

보조정리 3개가 필요하다. 대부분 well-known인 것 같다. 

그래프 \(H\)의 채색수를 \(\chi(H)\)라 하고, 최대 독립집합의 크기를 \(\alpha(H)\)라 하자.

Lemma 1. \(\chi(H) \cdot \alpha(H) \ge |V(H)|\)가 성립한다. 

Proof of Lemma 1. \(\chi(H)\)개의 색깔로 그래프를 색칠하면, 각 색으로 칠해진 정점의 집합은 각각 독립집합이 된다. 

이제 비둘기집의 원리를 적용하면 증명이 간단하게 끝난다.

Lemma 2. \(H\)의 적당한 부분그래프 \(H'\)이 존재하여, \(H'\)의 각 정점의 차수가 \(\chi(H)-1\) 이상이다. 

Proof of Lemma 2. 채색수를 유지하면서 정점을 삭제하는 것을 반복하자. 이 과정이 멈추면, 어떤 정점을 삭제해도 채색수가 감소하는 그래프를 얻게 된다. 이 그래프를 \(H'\)이라 하면, \(H'\)이 원하는 조건을 만족함을 보이자.

\(H'\)에 속하는 정점 \(v\)가 있어, \(H'\)에서 \(v\)의 차수 \(d\)가 \(\chi(H)-2\) 이하라고 가정하자. 

한편, \(H'\)의 성질에 의해서 \(H' - \{v\}\)는 \(\chi(H)-1\)개의 색으로 색칠할 수 있다. 

이제 \(d \le \chi(H)-2\)가 성립하므로, \(H' - \{v\}\)를 \(\chi(H)-1\)개의 색으로 색칠한 뒤 \(v\)를 적당한 색으로 칠해서 \(H'\) 전체를 \(\chi(H)-1\)개의 색으로 칠할 수 있게 된다. 그런데 \(\chi(H) = \chi(H')\)이 성립하므로, 이는 모순이다.

Lemma 3. \(H\)의 각 정점의 차수가 \(n-1\) 이상이면, \(H\)는 임의의 정점 \(n\)개를 가진 트리 \(T_n\)을 부분그래프로 가진다.

Proof of Lemma 3. \(n\)에 대한 귀납법. \(n \le 2\)까지는 자명하다. 

이제 임의의 정점 \(n\)개를 가진 트리 \(T_n\)을 하나 준비하고, 트리의 리프 노드 \(v\)를 하나 잡자.

귀납 가정에 의해서, \(H\)는 \(T_n - \{v\}\)를 포함한다. 한편, \(H\)의 각 정점의 차수가 \(n-1\) 이상이므로 적당하게 리프 노드 \(v\)를 \(H\)에서 찾은 \(T_n - \{v\}\)에 붙일 수 있다. 그러니 \(H\)는 \(T_n\)을 포함하고, 귀납법에 의해서 증명 끝.

이제 모든 준비가 끝났다. 본격적인 증명을 시작하자.

\(\overline{G}\)가 \(K_m\)을 포함하지 않는다는 것은 \(\alpha(G) < m\)이 성립한다는 것과 동치이다.

\(|V(G)|=(n-1)(m-1)+1\)이니, Lemma 1에 의해서 \(\chi(G) \ge n\)을 얻는다. 

Lemma 2에 의해서, \(G\)의 부분그래프 \(H\)가 존재하여 \(H\)의 각 정점의 차수가 \(n-1\) 이상이다.

Lemma 3에 의해서, \(H\)는 \(T_n\)을 부분그래프로 가진다. 즉, \(G\)는 \(T_n\)을 부분그래프로 가진다.

여기서 \(R(T_n, K_m) \le (n-1)(m-1)+1\)을 얻고, 이제 \(R(T_n, K_m) = (n-1)(m-1)+1\)을 얻어 증명 끝.

정말 간단하게, 의식의 흐름대로 쓰려고 한다. 종이 안 쓰고 글 쓰면서 푼 거라 깔끔하지는 않다.

이번에 29, 30이 진짜 쉽긴 한 것 같다 ㅋㅋ; 번호는 짝수 기준. 

20번.

• 앞면이 5번 이상 나오면 무조건 연속해서 나오는 경우가 있다.
• 여기서 \(\binom{7}{5}+\binom{7}{6}+\binom{7}{7} = 29\)개.
  
• 앞면이 4번 나오면, 한 경우를 제외하면 연속해서 나오는 경우가 있다.
• 여기서 \(\binom{7}{4}-1 = 34\)개.
• 앞면이 3번 나오는 경우를 보자. 전체 \(35\)개 중, 연속해서 나오지 않는 경우는 몇 개?
• \(1 \le x_1 < x_2 - 1 < x_3 - 2 \le 5\)로 생각하면 \(\binom{5}{3} = 10\)개.
• 그러니 총 \(29+34+35-10 = 88\)개. 답은 \(\frac{88}{2^7} = \frac{11}{16}\)이니 1번.

21번. 

• 절댓값과 미분 가능성에 관한 문제는 정말 많이 나오는 것 같다.
  
• 핵심은 절댓값 안에 있는 값이 0인 경우에, 도함수가 0이어야 한다는 것이다.
• 일단 \(f(x) = e^t(x-t)+e^t\)라는 것은 쉽게 알 수 있다.
• 그러니 우리는 \(|e^t(x-t)+e^t + k - \ln x|\)에 대하여 고민해야 한다.
• 일단 \(h(x) = e^t(x-t) + e^t + k - \ln x\)를 보자.
• \(h'(x) = e^t - \frac{1}{x}\)이니, \(h\)는 감소 후 증가한다.
• \(h\)의 최솟값이 \(0\) 이상이면, 문제 없다.
• \(h\)의 최솟값이 음수면, \(h(x)=0\)인 지점에서 \(h'(x)=0\)이어야 한다.
• 그런데 이러면 결국에는 \(h(x)=0\)인 지점이 그래프 개형상 극점이어야 한다.
• 결론: \(h\)의 최솟값이 \(0\) 이상이어야 한다.
• \(h\)의 최솟값은 \(x = e^{-t}\)에서 얻어진다. 
• 즉, \(h(e^{-t}) = 0\)이 되도록 하는 \(k\)의 값이 \(g(t)\)다.
• 정리하면 \(g(t) = (t-1)e^t - (t+1)\)을 얻는다.
• 이제 \(g\)의 그래프 개형을 그리면, (ㄱ)이 참임을 확인할 수 있다. 
• \(g\)가 연속이며, \(g\)의 최솟값이 음수이니까 (ㄱ)이 참임은 자명하다.
• (ㄴ)도 쉽게 확인할 수 있다. \((c-1)e^c = (c+1)\)이면, \((-c-1)e^{-c} = (-c+1)\)이다. 간단 식 조작.
• 마지막으로 (ㄷ)을 보자. \(g(x)\)의 개형을 다시 생각해보자.
• \(m\)이 최소라는 것은 \(g(\alpha) = g(\beta) = 0\)이라는 것이다.
• 이제 \(g'(x) = xe^x - 1\)임을 생각하면, \(\displaystyle \frac{1+g'(\beta)}{1+g'(\alpha)} = \frac{\beta e^{\beta}}{\alpha e^{\alpha}}\)다.
• 그런데 우리는 (ㄴ)에서 \(\alpha = -\beta\)임을 얻었다. 
• 그러니 이 식은 다시 \(-e^{2\beta}\)로 바뀐다. 이제 확인해야 하는 것은 \(\beta > 1\)인지 여부다.
• 이것은 매우 쉬운 일이다. \(\beta > 1\)임을 쉽게 확인할 수 있고, 결론적으로 (ㄷ)도 참이다. 답은 5번.

29번.

• 구면 위의 점 \((a,b,c)\)에서 그은 접평면의 방정식은 \(ax+by+cz=1\)이다.
• 그러니 접점을 찾으려면, \(a^2+b^2+c^2=3a-3b+3c=-2a+7b-2c=1\)인 \((a,b,c)\)를 찾으면 된다.
• \(b, c\)를 \(a\)에 대하여 표현한 뒤, \(a\)에 대한 이차방정식을 풀면 된다.
• 실제로 접점이 될 수 있는 두 점을 계산할 수 있다.
• 이제 사면체의 부피를 계산하면 되는데 고등학교 과정 내에서 쓰는 방법으로 적당히 계산하면 된다.
• 나는 귀찮아서 wolframalpha + determinant 썼다. 아마 \(\frac{20}{9} \sqrt{3}\)이 나와서 답이 \(29\).  

30번.

• 직관적으로, 한 점에서 만나려면, 그 점에서 두 함수의 값과 도함수가 모두 같아야 한다.
• 직관을 엄밀하게 설명하고 싶다면, 볼록/오목성을 조금만 생각해보면 알 수 있다.
• \(t^3\ln(x-t) = 2e^{x-a}\), \(\frac{t^3}{x-t} = 2e^{x-a}\)인 \(x\)가 있다.
• \((x-t)\ln(x-t) =1\)을 여기서 얻는다. 
• 그런데 \(h(x) = x\ln x\)의 개형을 생각해보면, \(x \ln x =1\)을 만족하는 실수 \(x\)는 유일하다.
• 이 값을 \(u\)라 설정하면, \(x-t=u\)가 강제된다. 
• 다시 대입하면, \(\frac{t^3}{u}  = 2e^{t+u-a}\)를 얻고, 정리하면 \( f(t)=a = t+u - \ln \frac{t^3}{2u}\)다.
• 이를 \(t\)에 대해서 미분하면, \(f'(t) = 1 - \frac{3}{t}\)를 얻는다. 이제 계산하면 답은 \(64\).

문제 (문제 링크)

\(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으로 붙여주면 된다.