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