rkm0959

문제

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

이번 포스팅에서는 다음 정리를 증명한다. 

Theorem 3: Lévy-Steinitz Theorem (Lévy 1905, Steinitz 1913, Gross 1917) 

\(\mathbb{R}^n\)의 벡터들로 이루어진 series \(\sum v_n\)에 대하여, 도달 가능한 극한값들의 집합 \(V\)는 공집합이거나, 적당한 \(\mathbb{R}^n\)의 subspace \(W\)과 \(v \in \mathbb{R}^n\)에 대해 \(v+W\)꼴로 표현된다. 즉, \(V\)는 공집합이거나 \(\mathbb{R}^n\)의 subspace를 적당히 translate한 형태이다.

먼저, Theorem 3을 증명하기 위해 자주 사용할 정리를 하나 소개한다. 

Theorem 4: Polygonal Confinement Theorem

임의의 자연수 \(n\)에 대하여, 적당한 상수 \(C_n\)이 존재하여 다음이 성립한다. 

\(v_1, v_2, \cdots v_M\)이 임의의 \(1 \le i \le M\)에 대하여 \(|v_i| \le 1\)을 만족하고, \(v_1+v_2+ \cdots v_M = \vec{0}\)을 만족하는 \(\mathbb{R}^n\)의 벡터들이라면, \( (2, 3, \cdots M) \)의 적당한 permutation \(P\)가 존재하여 $$ \left| v_1 + \sum_{i=2}^j v_{P(i)} \right| \le C_n $$이 모든 \(2 \le j \le M\)에 대해 성립한다. 또한, \(C_1=1\)과 \(C_n = \sqrt{4C^2_{n-1}+1} \) (단, \(n \ge 2\))으로 잡아도 괜찮다.  

Proof of Theorem 4: \(n\)에 대한 귀납법으로 문제를 해결하자. 우선 \(n=1\)부터 처리하자. 

\(n=1\)인 경우에는, \(v_1, v_2, \cdots v_M\)은 모두 절댓값이 \(1\) 이하인 실수다.

만약 \(v_1 > 0\)이라면, 부분합이 \(0\) 미만이 되는 시점까지 \(v_i \le 0\)인 \(v_i\)들을 더해준다. 

부분합이 음수가 되면, 다시 부분합이 \(0\) 초과가 되는 시점까지 \(v_i \ge 0\)인 \(v_i\)들을 더해준다.

모든 실수들의 합이 \(0\)이기 때문에 이 방법을 통해서 모든 벡터를 한 번씩 나열할 수 있다.

또한, 각 \(v_i\)들은 절댓값이 \(1\) 이하이므로, 부분합은 절대 절댓값이 \(1\) 초과가 될 수 없다. 

\(v_1 \le 0\)인 경우도 마찬가지 알고리즘으로 permutation을 찾을 수 있다. 그러므로 \(C_1=1\)을 잡아도 ok.

이제 귀납적으로 생각해보자. \(n-1\)에 대한 명제에서 \(n\)에 대한 명제로 넘어가보자. 

벡터의 개수가 유한하므로, \(v_1\)을 포함하는 벡터들의 합 중 가장 길이가 긴 것을 생각하자. 

이를 \(L=v_1+u_1+u_2+ \cdots + u_s\)라 하자. 단, \(\{u_1, u_2, \cdots u_s \} \subset \{v_2, v_3, \cdots v_M\} \)이다. 

\(L\)에서 등장하지 않은 벡터들을 \(w_1, w_2, \cdots w_t\)라 하자. 즉, \(L+w_1+w_2+ \cdots w_t = \vec{0} \)이다. 

Claim 1: 각 \(1 \le i \le s\)에 대해서, \(u_i \cdot L \ge 0\)이 성립한다.

Claim 2: \(v_1 \cdot L \ge 0\)이 성립한다.

Claim 3: 각 \(1 \le i \le t\)에 대해서, \(w_i \cdot L \le 0\)이 성립한다.

이 Claim들의 증명은 아주 간단하므로 sketch만 한다. 모두 귀류법이고, 모순은 다음과 같이 발생한다. 

Claim 1: \(u_i\) 빼면 길이가 더 길어진다.

Claim 2: \(v_1+u_1+u_2+\cdots +u_s\)보다 \(v_1+w_1 +w_2 +\cdots + w_t\)가 더 길어진다. 

Claim 3: \(w_i\) 추가하면 길이가 더 길어진다. 

본격적으로 귀납 가정을 쓸 준비를 하자. \(L^\perp = \{v \in \mathbb{R}^n | v \cdot L = 0\} \)를 생각하자. 

\(L = \vec{0}\)이면 결과는 자명하므로 이 경우는 넘어가고, \(L \neq \vec{0}\)인 경우를 보자. 

그러면 \(L^\perp\)는 \(n-1\)차원 벡터공간이고, 여기서 귀납 가정을 사용할 각을 생각할 수 있다. 

\(\mathbb{R}^n\)의 벡터 \(v\)에 대하여, \(v' = v - \frac{v \cdot L}{|L|^2} L \)을 \(v\)의 \(L^\perp\) 성분이라고 하자. 

그러면 정의에 의해 \(v'_1 + u'_1 + u'_2 + \cdots u'_s = w'_1 + w'_2 + \cdots w'_t = \vec{0}\)이다. 

게다가, \(v'_1, u'_1, u'_2, \cdots u'_s, w'_1, w'_2, \cdots w'_t\)는 모두 \(n-1\)차원 벡터공간 \(L^\perp\)에 속하는 벡터들이다.

그러므로, 차원이 \(n-1\)인 경우에 대한 귀납 가정을 쓰기 위해 필요한 조건을 모두 갖추고 있다! (why?)

귀납 가정에 의하여, \((1,2, \cdots s)\)의 적당한 permutation \(Q\)가 있어 $$ \left| v'_1 + \sum_{i=1}^j u'_{Q(i)} \right| \le C_{n-1} $$이 모든 \(1 \le j \le s\)에 대해 성립한다. 

귀납 가정에 의하여, \((2, 3, \cdots t)\)의 적당한 permutation \(R\)가 있어 $$ \left| w'_1 + \sum_{i=2}^j w'_{R(i)} \right| \le C_{n-1} $$이 모든 \(2 \le j \le t\)에 대해 성립한다. \(R(1)=1\)이라 하자.  

이제 남은 것은 이를 합치는 것 뿐이다. \(v_1, u_1, u_2, \cdots u_s\)는 모두 \(v_1, u_{Q(1)}, u_{Q(2)}, \cdots u_{Q(s)} \) 순서로 등장하게 하고, \(w_1, w_2, \cdots w_t\)는 모두 \(w_{R(1)}, w_{R(2)}, \cdots w_{R(t)}\) 순서로 등장하게 하자. 

이제 \(L^\perp\)에 어떤 부분합을 사영시키면 그 길이는 최대 \(2C_{n-1}\)임이 보장된다.

문제는 \(L\) 방향으로 사영시킨 길이를 bound시키는 건데, 여기서 Claim 1, 2, 3이 역할을 한다. 

모든 벡터들의 합이 \(\vec{0}\)이므로, \(L\)에 해당하는 성분의 합도 \(0\)이다. 즉, 앞서 \(n=1\)에 대해 Theorem 4를 증명한 것과 동일한 방법으로 \(u_i\)들과 \(w_i\)들을 적당히 번갈아가며 배치해, \(L\)에 어떤 부분합을 사영시키면 그 길이가 최대 \(1\)이 되도록 보장할 수 있다.

여기서 \(n=1\) 증명에서 '0 이상' 역할을 \(v_1\)과 \(u_i\)들이, '0 이하' 역할을 \(w_i\)들이 한다. 

다시 강조하지만 \(u_i\)들 사이의 순서는 앞서 말했듯이 유지한다. \(w_i\)들 사이의 순서도 마찬가지로 유지한다 

이렇게 해서 permutation을 잡아주면 임의의 부분합의 길이는 최대 \(\sqrt{4C^2_{n-1}+1}\)임을 알 수 있다. 증명 끝. 

이제 Polygonal Confinement Theorem을 활용해서, 다양한 보조정리/정리들을 이끌어내보자. 

Lemma 5: \(v_1, v_2, \cdots v_m \in \mathbb{R}^n\)은 \(|v_1+v_2+ \cdots v_m| \le \epsilon\)과 \(|v_i| \le \epsilon \) (\(1 \le i \le m \))를 만족한다. 

그러면, \((1,2, \cdots m)\)의 permutation \(P\)가 존재하여, $$ \left| v_{P(1)}+v_{P(2)} + \cdots v_{P(j)} \right| \le \epsilon (C_n + 1) $$가 모든 \(1 \le j \le m\)에 대해서 성립한다. 

Proof of Lemma 5: \(v_{m+1} = -v_1 - v_2 - \cdots - v_m\)을 잡자. 이제 \(v_1 + v_2+ \cdots v_{m+1} = \vec{0}\)이다. 

또한, 각 벡터 \(v_1, v_2, \cdots v_{m+1}\)의 크기는 최대 \(\epsilon\)이다. \(\frac{1}{\epsilon} v_1, \frac{1}{\epsilon} v_2, \cdots \frac{1}{\epsilon} v_{m+1}\)에 대해서 Theorem 4를 적용해보자. 

적당한 permutation이 존재하여 \(v_{P(i)}\)들의 임의의 부분합의 크기가 \(\epsilon C_n\)이하이도록 할 수 있다.

이제 여기서 \(v_{m+1}\)을 제거해야 하는데, 이미 \(\left|v_{m+1}\right| \le \epsilon\)을 알고 있으니 삼각부등식으로 처리할 수 있다. 

삼각부등식을 적용하면, 결국 임의의 부분합의 크기가 \(\epsilon (C_n+1)\) 이하가 되도록 할 수 있음을 확인할 수 있다. 

Theorem 6: Rearrangement Theorem 

\(\{v_i\}\)는 \(\mathbb{R}^n\)에 속한 벡터들의 수열이다. 이 수열의 부분합을 \(s_1, s_2, \cdots \)라 하자. 

만약 \(S \in \mathbb{R}^n\)으로 수렴하는 \(\{s_i\}\)의 부분수열이 존재하고, \(|v_n|\)이 \(n \rightarrow \infty\)에서 \(0\)으로 수렴한다면, 적당한 \(\{v_i\}\)의 rearrangement가 존재하여 rearrange된 수열의 합이 \(S\)로 수렴한다.  

Proof of Theorem 6: \(s_{m_1}, s_{m_2}, \cdots , s_{m_k}, \cdots \)가 \(S\)로 수렴한다고 하자.

핵심은 각 \(i=1, 2, \cdots\)에 대하여 \(v_{m_i+1} , v_{m_i+2}, \cdots v_{m_{i+1}}\)를 하나의 패키지로 보는 것이다. 

각 패키지에 속한 벡터들을 Lemma 5를 활용해 적당히 rearrange 하여, 각 \(m_k < T <m_{k+1}\)에 대해 \(s_T\)와 \(s_{m_k}\) 사이의 차이가 충분히 작도록 만드는 것이 핵심 아이디어다. 

\(\delta_k = |s_{m_k}-S| \)라 하면, \(\delta_k \rightarrow 0\)이다. 한편, $$ \left| \sum_{i=m_k+1}^{m_{k+1}-1} v_i \right| = \left| s_{m_{k+1}} - s_{m_k} - v_{m_{k+1}} \right| \le \delta_{k+1} + \delta_k + |v_{m_{k+1}}| $$이고, \( \epsilon_k = \text{max}(\delta_{k+1}+\delta_k, \text{sup}_{i \ge m_k} |v_i|) \)라 정의하면 \(\epsilon_k \rightarrow 0\)이고 앞선 관찰에 의해 $$ \left| \sum_{i=m_k+1}^{m_{k+1}-1} v_i \right| < 2 \epsilon_k $$이 성립한다. 

이제, Lemma 5에 의해 \((m_k+1, m_k+2, \cdots m_{k+1}-1)\)의 permutation \(P_k\)가 존재하여, $$ \left| \sum_{i=m_k+1}^r v_{P_k(i)} \right| \le 2\epsilon_k (C_n+1) $$가 모든 \(m_k+1 \le r \le m_{k+1}-1\)에 대해 성립한다. 

각 패키지를 저렇게 rearrange했다고 가정하자. \(m_k < T <m_{k+1}\)라고 하면, \(|s_T-S| \le \delta_k + 2\epsilon_k (C_n+1) \)가 성립함을 삼각부등식으로 쉽게 확인할 수 있다. 또한, 이를 통해 rearrange된 수열은 그 합이 \(S\)로 수렴하게 됨을 확인할 수 있다. 

Lemma 7: \(v_1, v_2, \cdots , v_m\)은 모두 \(\mathbb{R}^n\)의 벡터들이고, \(w=\sum_{i=1}^m v_i\)이다. \(t\)는 \(0<t<1\)을 만족하는 실수이며, \(|v_i| \le \epsilon\)가 모든 \(1 \le i \le m\)에 대하여 성립한다고 한다. 이때, 다음 둘 중 적어도 하나가 성립한다. 

1. \(|v_1 - tw| \le \epsilon \sqrt{C^2_{n-1}+1} \)

2. \((2,3, \cdots , m)\)의 적당한 permutation \(P\)과 \(2 \le r \le m\)이 존재하여, $$ \left| v_1 + \sum_{i=2}^r v_{P(i)} - tw \right| \le \epsilon \sqrt{C^2_{n-1}+1} $$

Proof of Lemma 7: \(w = \vec{0}\)인 경우는 자명하므로, \(w \neq \vec{0}\)을 가정하자.

\(n\)에 대한 귀납법으로 보이자. (Theorem 4의 증명 느낌이 많이 나는 증명이다.)

우선 \(n=1\)부터 보자. 일반성을 잃지 않고, \(w>0\)을 가정한다. 

\(v_1+v_2+ \cdots v_i > tw\)가 성립하는 최소의 \(i\)를 \(s\)라 하자. (\(i=m\)인 경우에 성립하니 최소의 \(i\)도 존재한다.)

그러면 \(v_1+v_2+ \cdots + v_{s-1} \le tw\)이므로, \(|v_1+v_2+ \cdots v_s - tw| \le \epsilon \)이 성립한다. 

\(w^\perp\)를 생각하자. \(v'\)를 \(v - \frac{w \cdot v}{|w|^2} w\)라 정의하면, \(v'_1 + v'_2 + \cdots + v'_m = \vec{0}\)이다.  

한편, \(|v_i| \le \epsilon\)이므로 \(|v'_i| \le \epsilon\)도 성립하고, Theorem 4에 의해 적당한 \((2,3, \cdots m)\)의 permutation \(P\)가 존재하여 $$ \left|v'_1 + \sum_{i=2}^j v'_{P(i)} \right| \le \epsilon C_{n-1} $$가 모든 \(2 \le j \le m\)에 대해 성립한다. 

또한, \( \sum_{i=1}^m \frac{v_{P(i)} \cdot w}{|w|} = |w| \)가 성립하므로, \(n=1\)인 경우를 생각하면 적당한 \(r\)이 있어 $$ \left| \sum_{i=1}^r \frac{v_{P(i)} \cdot w}{|w|} - t|w| \right| \le \epsilon$$이 성립한다. 여기서 \(P(1)=1\)이며, \(\frac{v_i \cdot w}{|w|} \le |v_i| \le \epsilon\)임에 주목하자. 

두 부등식은 각각 \(w\)와 수직한 성분, \(w\)와 평행한 성분에 대한 부등식을 보여준다. 

두 부등식을 합치면 \( \left| v_1 + \sum_{i=2}^r v_{P(i)} - tw \right| \le \epsilon \sqrt{C^2_{n-1}+1} \)을 바로 얻을 수 있다. 증명 끝. 

이제 모든 준비가 끝났다. 

Theorem 3: Lévy-Steinitz Theorem (Lévy 1905, Steinitz 1913, Gross 1917) 

\(\mathbb{R}^n\)의 벡터들로 이루어진 series \(\sum v_n\)에 대하여, 도달 가능한 극한값들의 집합 \(V\)는 공집합이거나, 적당한 \(\mathbb{R}^n\)의 subspace \(W\)과 \(v \in \mathbb{R}^n\)에 대해 \(v+W\)꼴로 표현된다. 즉, \(V\)는 공집합이거나 \(\mathbb{R}^n\)의 subspace를 적당히 translate한 형태이다.

Proof of Theorem 3: 기본 밑밥부터 깔아놓자. \(V\)가 공집합이 아니라고 가정하고, \(v \in V\)를 하나 가져온 후, \(v_1\)을 \(v_1- v\)로 교체하자. 그러면 \(0 \in V\)라고 가정할 수 있으며, 이제 \(V\)가 subspace임을 보이기만 하면 충분하다. 이를 위해서는 \(s_1, s_2 \in V \implies s_1+s_2 \in V\)를 보이고, \(s_1 \in V, t \in \mathbb{R} \implies ts_1 \in V\)를 보여야 한다. 

Step 1. \(s_1, s_2 \in V \implies s_1+s_2 \in V\)를 보이자. 

\(0\)으로 수렴하는 양의 실수로 이루어진 수열 \(\{\epsilon_m\}\)을 잡자. 

\(s_1\)으로 수렴하는 rearrangement가 존재하므로, 유한집합 \( I_1\)이 있어 \(1 \in I_1\)과 \(|\sum_{i \in I_1} v_i - s_1 | < \epsilon_1 \)을 만족한다. 

\(0\)으로 수렴하는 rearrangement가 존재하므로, 유한집합 \(J_1\)이 있어 \(I_1 \subseteq J_1\)과 \(|\sum_{i \in J_1} v_j| < \epsilon_1\)을 만족한다.

\(s_2\)으로 수렴하는 rearrangement가 존재하므로, 유한집합 \(K_1\)이 있어 \(J_1 \subseteq K_1\)과 \(|\sum_{i \in K_1} v_j - s_2| < \epsilon_1\)을 만족한다.

\(s_1\)으로 수렴하는 rearrangement가 존재하므로, 유한집합 \( I_2\)이 있어 \(K_1 \in I_2\)과 \(|\sum_{i \in I_2} v_i - s_1 | < \epsilon_2 \)을 만족한다. 

이를 반복해주면, 결국 $$ \{1,2, \cdots , m-1\} \subset K_{m-1} \subset I_m \subset J_m \subset K_m $$ $$\left |\sum_{i \in I_m} v_i - s_1 \right| < \epsilon_m \text{,                   } \left|\sum_{i \in J_m} v_i \right| < \epsilon_m \text{,                  } \left|\sum_{i \in K_m} v_i - s_2 \right| < \epsilon_m$$ 

이제 다음 순서로 벡터들을 배치한다. 

1. 먼저, \(I_1\)에 속한 벡터들을 배치한다.

2. 그 뒤에, \(J_1 \cap I^C_1\)에 속한 벡터들을 배치한다.

3. 그 뒤에, \(K_1 \cap J^C_1\)에 속한 벡터들을 배치한다.

4. 그 뒤에, \(I_2 \cap K^C_1\)에 속한 벡터들을 배치한다.

5. 이를 계속해서 반복한다. 

이렇게 벡터들을 배치하면, 하나의 rearrangement가 된다는 사실은 자명하다. 이 permutation을 \(P\)라 하자.

이제 \(i_m=|I_m|\), \(j_m=|J_m|\), \(k_m=|K_m|\)이라 하면 $$\left |\sum_{i=1}^{i_m} v_{P(i)} - s_1 \right| < \epsilon_m \text{,                   } \left|\sum_{i=1}^{j_m} v_{P(i)} \right| < \epsilon_m \text{,                  } \left|\sum_{i=1}^{k_m} v_{P(i)} - s_2 \right| < \epsilon_m$$임을 바로 확인할 수 있다. 

삼각부등식을 사용해주면, $$ \left| \sum_{i=1}^{i_m} v_{P(i)} + \sum_{i=j_m+1}^{k_m} v_{P(i)} - (s_1+s_2) \right| < 3\epsilon_m $$이 성립함을 확인할 수 있다. 이제 Rearrangement Theorem을 사용할 각을 재자. 

여기서 \(v_{P(j_m+1)}, v_{P(j_m+2)}, \cdots v_{P(k_m)}\)와 \(v_{P(i_m+1)}, v_{P(i_m+2)} , \cdots v_{P(j_m)} \)을 통째로 자리바꿈하자. 

우선 현재 벡터들의 배치는 여전히 하나의 rearrangement이다.

또한, 이 최종 수열의 부분합 수열을 생각하면 \(s_1+s_2\)로 수렴하는 부분수열이 존재한다. 

그러므로, Rearrangement Theorem에 의해 \(s_1+s_2 \in V\)임을 확인할 수 있다. Step 1 끝. 

Step 2: \(s_1 \in V, t \in \mathbb{R} \implies ts_1 \in V\)를 보이자. 

2개의 포스팅에 걸쳐서, \( \mathbb{R}^n \) 벡터의 수열들과, 이들의 Rearrangement의 수렴성에 대해서 다룬다.

이번 글에서는 \(n=1\)인 경우, 즉 우리가 익숙한 실수 수열들의 Rearrangement와 수렴성에 대해서 다룬다.

그리고 이를 기반으로 해서, 일반적인 \( \mathbb{R}^n \) 벡터의 수열들에 대한 여러 직관/아이디어를 다룬다.

먼저 Rearrangement의 정의를 짚고 넘어가자. Rudin p. 75에 있는 Definition 3.52를 그대로 가져온다.

Definition: \(k_n\) (\(n=1,2, \cdots \))은 모든 자연수가 정확히 한 번씩 등장하는 수열이다. 즉, \(k_n\)은 자연수의 집합에서 자연수의 집합으로 가는 전단사함수라고 볼 수 있다. 이제 \(a'_n=a_{k_n}\)이라 하면, \(\sum a'_n\)은 \(\sum a_n\)의 Rearrangement라고 한다. 

Theorem 1: (Riemann's Rearrangement Theorem) 

(1) \(\sum a_n\)이 절대수렴하는 실수 series라면, 모든 Rearrangement \(\sum a'_n\)이 수렴하고, 같은 값으로 수렴한다. 

(2) \(\sum a_n\)이 수렴하지만 절대수렴하지는 않는 실수 series라 하자. 이제 $$ -\infty \le \alpha \le \beta \le \infty$$인 \(\alpha, \beta\)를 잡으면, 적당한 Rearrangement \(\sum a'_n\)가 존재하여 다음이 성립한다. $$ \lim_{n \rightarrow \infty} \text{inf  } s'_n = \alpha, \text{     } \lim_{n \rightarrow \infty} \text{sup  } s'_n = \beta $$ 물론 여기서 \(s'_n = \sum_{i=1}^n a'_i \)는 Rearrangement의 Partial Sum이다. 

Proof of Theorem 1:  

(1) \(\sum |a_i|\)가 수렴하므로, 임의의 \(\epsilon > 0\)에 대해 \(m \ge n \ge N\)이면 \(\sum_{i=n}^m |a_i| < \epsilon\)이 성립하는 적당한 자연수 \(N\)이 존재한다. 이제 \(k_1, k_2, \cdots k_p\)에 \(1, 2, \cdots N\)이 모두 포함되는 자연수 \(p\)를 설정하자. 앞선 Definition에서 쓴 notation을 그대로 가져왔다. 이제 \(n > p\)라면, \(s_n - s'_n = \sum_{i=1}^n (a_i - a'_i) \)에서 \(a_1, a_2, \cdots a_N\)은 전부 상쇄되며, \(N\) 이상의 index에 해당하는 수열의 값들은 식에서 최대 한 번 등장한다. 직접 써보면서 생각하자. 결론적으로 \(|s_n-s'_n| < \epsilon \)이고, 결국 \(\epsilon - \delta\) 정의에 의해 \(\{s'_n\}\)도 \(\{s_n\}\)과 같은 값으로 수렴한다. 증명에서 \(a_i\)가 실수임을 사실상 쓰지 않았다. 즉, \(\mathbb{R}^n\)에서도 이 정리는 성립.  

(2) \(p_n = \frac{a_n + |a_n|}{2}\), \(q_n = \frac{|a_n|-a_n}{2}\)라 하자. 그러면 \(p_n-q_n = a_n\), \(p_n+q_n = |a_n|\)이며 \(p_n, q_n \ge 0\)이다. \(\sum a_n\)은 수렴하고, \(\sum |a_n|\)은 발산하므로, \(\sum p_n\)과 \(\sum q_n\)은 모두 발산한다. 즉, 이 친구들은 unbounded. 한편, \(P_1, P_2, \cdots \)를 \(a_n\)의 nonnegative term을 등장 순서대로 나열한 것이라고 하고, \(Q_1, Q_2, \cdots \)를 \(a_n\)의 negative term의 절댓값을 등장 순서대로 나열한 것이라고 하자. 그러면 \(P_i\)들은 \(p_i\)들과 zero term에서만 차이가 나고, \(Q_i\)들은 \(q_i\)들과 zero term에서만 차이가 난다. \(a_i\)의 부호에 따라서, \(p_i, q_i\)가 어떻게 표현되는 지를 생각해보자. 아무튼 여기서 \(\sum P_i\)와 \(\sum Q_i\)는 발산함을 알 수 있다. 이제 우리의 목표는 \(P\)에서 원소를 몇 개 배치, \(Q\)에서 원소를 몇 개 배치하는 것을 반복하여, 부분합의 값이 \(\alpha\)와 \(\beta\) 사이를 돌도록 하는 것이다. 이를 위해서, 자연수로 이루어진 증가수열 \(m_n, k_n\)을 적당히 잡아서, $$P_1 + P_2 + \cdots P_{m_1} - Q_1 - Q_2 - \cdots Q_{k_1} + P_{m_1+1} + P_{m_1+2} + \cdots + P_{m_2} - Q_{k_1+1} - Q_{k_1+2} - \cdots - Q_{k_2} + \cdots $$ 형태의 Rearrangement를 만들 것이다. 

이를 위해서, 실수 수열 \(\{\alpha_n\}, \{\beta_n\} \)를 잘 잡아서, \(\alpha_n \rightarrow \alpha\), \(\beta_n \rightarrow \beta\)가 성립하고, \(i<j\)면 \(a_i \le a_j \le \alpha \le \beta \le b_j \le b_i\)가 성립하도록 하자. 또한, \(b_1 > 0\)이 성립하도록 설정하자. 이제 \(m_1, k_1\)은 $$P_1 + P_2 + \cdots P_{m_1} > \beta_1, \text{    } P_1 + P_2 + \cdots P_{m_1} - Q_1 - Q_2 - \cdots Q_{k_1} < \alpha_1$$이 성립하는 최소의 자연수로 설정한다. 이 방식으로 \(m_n, k_n\)을 계속해서 잡아나간다. 이것이 가능한 이유는 \(\sum P_i\)와 \(\sum Q_i\)는 발산하기 때문이다. 이제 이렇게 Rearrangement를 잡아주면, \(P_{m_n}\)까지 더한 Partial Sum은 \(n \rightarrow \infty\)에서 \(\beta\)로 수렴하고, \(Q_{k_n}\)까지 더한 Partial Sum은 \(n \rightarrow \infty\)에서 \(\alpha\)로 수렴함을 확인할 수 있다. 또한, $$ \lim_{n \rightarrow \infty} \text{inf  } s'_n = \alpha, \text{     } \lim_{n \rightarrow \infty} \text{sup  } s'_n = \beta $$까지 직접 확인할 수 있다. 확인하는 과정은 크게 어렵지 않고, routine한 과정이므로 생략한다. 증명 끝. 

이제 우리는 \(\mathbb{R}^n\)의 벡터로 이루어진 series와 이들의 Rearrangement에 대해 생각한다. 

Theorem 1을 통하여 우리는 \(\mathbb{R}\)의 원소들로 이루어진 series가 수렴할 경우, 절대수렴 여부에 따라서 그 Rearrangement가 가질 수 있는 '범위'가 달라진다는 것을 확인했다. 급수가 절대수렴할 경우, 어떻게 Rearrangement를 잡더라도 그 급수는 기존 급수와 같은 값으로 수렴하며, 이는 \(\mathbb{R}^n\)에서도 동일하다. 급수가 조건수렴할 경우, Rearrangement를 적당히 잘 잡아서 새로운 수열이 가지는 subsequential limit들의 superior, inferior까지도 우리 마음대로 설정할 수 있음을 보였다.

이제 다음과 같은 질문이 자연스럽게 나올 수 있을 것이다.

Question 2:

\(\mathbb{R}^n\)의 벡터로 이루어진 series \(\sum a_n\)이 있다. 이제, 이 series의 적당한 Rearrangement \(\sum a'_n\)이 존재해 \(\sum a'_n\)이 \(v \in \mathbb{R}^n \)으로 수렴하면, \(v\)를 "도달 가능한 극한값"이라 하자. 도달 가능한 극한값의 집합을 \(V\)라 하면, \(V\)는 어떤 형태일까?   

일단 \(n=1\)인 경우, \(V\)는 '공집합', '점', 그리고 '수직선 전체' 중 하나임을 확인하자. 

조금 생각을 해보면, 만약 급수의 모든 항이 \(\mathbb{R}^n\)의 subspace \(W\)의 원소라면, (즉, \(a_n \in W\)) 어떻게 Rearrangement를 하더라도 Rearrangement의 수렴값 \(v \in \mathbb{R}^n\)이 존재한다면 \(v \in W\)가 성립한다는 사실을 알 수 있다.  

이 사실은 다양한 방법으로 설명할 수 있다. \(W\)의 orthogonal complement를 생각하는 것이 하나의 방법이다. Series의 각 원소들이 \(W\)의 orthogonal complement의 basis의 원소들과 모두 수직하므로, 모든 Series의 부분합도 이 성질을 만족하고, (dot product를 생각하자!) 결론적으로 \(v\)도 이 성질을 가져가게 된다. Orthogonal Complement의 Orthogonal Complement는 자기 자신임이 잘 알려져 있고, 결국 \(v\)는 \(W\) 안에 속하게 된다. 이렇게 증명 끝. 또 다른 방법으로는, subspace가 closed한 집합임을 설명하는 방법이 있다. 이것도 잘 알려진 사실이다.

이제 다시 \(n=1\)의 경우를 보자. \(V\)가 일종의 vector space 형태로 나올 것이라는 느낌이 든다. 

여기서 한 층 더 깊게 생각해보자. 조건수렴하는 실수 series \(\sum a_n\)이 있다고 하자. 

Riemann Rearrangement Theorem에 의해, 우리는 이 series를 잘 Rearrange하여, 원하는 곳으로 수렴시킬 수 있다. 

이제 \(b_n = (a_n + \frac{1}{2^n}, 2a_n, 3a_n - \frac{1}{2^n}) \)로 정의된 \(\mathbb{R}^3\)의 벡터들을 생각하자. 

이제부터는 \(\sum b_n\)을 생각하자. 이 series를 잘 Rearrange하면, 어떤 수렴값을 얻을 수 있을까?

조금 고민해보면, 결국 \(V\)는 \((1,0,-1)+t(1,2,3)\) 형태의 벡터로 이루어졌음을 알 수 있다. 

여기서 series의 합은 \(n=1\)부터 시작한다고 가정했다. 아무튼 우리는 \(V\)의 형태에 대한 직관을 하나 더 얻었다.     

이제 우리의 직관이 참임을 증명해보자. 이 증명은 후속 포스팅에서 다룬다. 우리의 최종 목표는 다음과 같다. 

Theorem 3: Lévy-Steinitz Theorem (Lévy 1905, Steinitz 1913, Gross 1917) 

\(\mathbb{R}^n\)의 벡터들로 이루어진 series \(\sum a_n\)에 대하여, 도달 가능한 극한값들의 집합 \(V\)는 공집합이거나, 적당한 \(\mathbb{R}^n\)의 subspace \(W\)과 \(v \in \mathbb{R}^n\)에 대해 \(v+W\)꼴로 표현된다. 즉, \(V\)는 공집합이거나 \(\mathbb{R}^n\)의 subspace를 적당히 translate한 형태이다.

D-1

시험을 하루 앞두고 마지막 점검에 들어갔다. 컨디션이 많이 안 좋아보였다. 

문제 푸는 방법도 잘 안 보이고... 계산도 계속 실수를 해서 자신감이 조금 떨어지고... 정신적으로 힘들었다.

자기 직전에 멘탈 마지막으로 잡으려고 레미제라블의 'One Day More'를 들었는데, 멘탈이 더 깨졌다.

솔직히 내일이 심판의 날이네 주의 뜻을 알 수 있는 날이네 뭐네 이러는데 멘탈에 도움이 될리가 없다 ㅋㅋ

잠도 더럽게 안 와서 12시 근처에 잔 것 같다. 시작되지도 않은 시험에 크게 말린 느낌이 들어서 걱정이 앞섰다.

D-Day

새벽 5시에 일어나서 씻고 바로 출발, 새벽 6시 30분 정도에 익숙한 수리과학부 건물에 도착했다.

잠을 좀 깨고 정신을 차려서 면접 건물로 이동하고, 학교 선생님의 격려 속에서 친구와 같이 면접 대기실로 갔다.

면접 장소인 4층에 올라가보니, 복도에 책상이 깔려 있었다. 여기서부터 약간 소름 ㅋㅋ

대기실로 들어가서, 주변에 아는 사람이 있나 좀 둘러보았더니, 면접자 라인업이 상당히 살벌했다.

특히 서울과학고에서 온 친구들은 거를 타선이 없을 정도로 수학을 잘하는 친구들만 와서 무서웠다.

면접을 보는 순서를 곧 알려주셨고, 내가 5번째 순서로 면접을 본다는 사실을 확인했다.

대기하는 동안에는 내가 전날 확인해둔 자소서 관련 내용을 다시 상기하고, 프린트 몇 개 꺼내서 읽었다. 

면접 대기실의 분위기가 그렇게 무겁지는 않아서 좋았던 것 같다. 학생들의 긴장을 풀어주기 위해 많이 노력하신 것 같다.

아무튼 내가 면접을 보는 시간인 9:45는 빠르게 다가왔고, 운명의 45분이 시작되었다. 

문제

1. \( A(-10,2), B(10,2)\)가 \(xy\) 평면 위에 있다. 또한, 점 \(C, D\)는 \(x\)축 위의 점이다. 

(1) \( AC + CD + DB\)가 최소일 때, \(C, D\)의 좌표를 구하시오.

(2) \( 0< k \le 1\)인 \(k\)에 대해 \(AC+kCD+DB\)가 최소가 되도록 \(C, D\)를 잡자. 

이때, \(C\)와 \(D\)가 \(y\)축에 대해 대칭임을 보이시오. 

(3) \(k\)가 1에서 시작하여 감소하다 어느 값이 되면 \(AC+kCD+DB\)의 값을 최소로 하는 점 \(C, D\)가 움직이기 시작한다. \(C, D\)가 움직이기 시작하게 되는 \(k\)의 값을 구하시오.

2. \(xy\) 평면에서 다음과 같은 영역 \(S, T\)를 정의하자. 

$$ S = \{(x,y) | |y| > x^2\} $$ $$ T = \{(x,y)|0<|y|<|x| \} $$ 또한, 시행 \((P)\)와 \((Q)\)를 다음과 같이 정의하자. 

시행 \((P)\): \(0\)이 아닌 정수 \(m\)을 선택하고, \((x,y)\)를 \((x^2+2my,y)\)로 옮긴다.

시행 \((Q)\): \(0\)이 아닌 정수 \(n\)을 선택하고, \((x,y)\)를 \((\sqrt{|x|},y+2nx)\)로 옮긴다.

(1) \(S\)에 속한 점은 시행 \(P\)를 통해 \(T\)의 점으로 옮겨진다는 것을 보이시오.

(2) '되돌이점'을 다음과 같이 정의하자. 

점 \((x,y)\)에 대하여, 시행 \((Q)\)와 시행 \((P)\)를 번갈아 진행했을 때 다시 원위치로 돌아올 수 있는 점들을 되돌이점이라고 한다. 단, 시행은 반드시 시행 \((Q)\)로 시작되어야 한다. 

(예시) \((0,0) \rightarrow (0,0)\), (\(n=1\) 선택하여 시행 \((Q)\))

\((1,2) \rightarrow (1,0) \rightarrow (1,0) \rightarrow (1,2)\), (\(n=-1\), \(m=1\), \(n=1\)을 순서대로 선택하여 \((Q), (P), (Q)\) 시행)

그러므로, \((0,0), (1,2)\)는 모두 되돌이점이다. 이제 \((1,0)\)은 되돌이점인지 판단하시오. 

풀이

1번을 보고 약간 당황했다. 이런 기하문제가 입시에 나올 것이라고는 생각하지 못했다.

우선 1-(1)은 \(B\)를 \(x\)축 기준으로 대칭시킨 다음, 삼각부등식을 적용하여 해결할 수 있다. 

\(B'(10,-2)\)를 잡으면, 대칭성과 삼각부등식에 의해서 다음이 성립함을 확인할 수 있다.

$$ AC + CD + DB = AC + CD + DB' \ge AB' $$ 등호는 \(A, C, D, B'\)이 한 직선 위에 있을 때 성립하며, 이 경우는 \(C, D\)가 원점일 때이다. 

1-(2)는 초반에 방향을 잘못 잡으면 말릴 수 있는 문제였다. \(C, D\)가 원점을 기준으로 반대 방향에 있어야 한다는 사실을 가정한다면, \(C, D\)는 각각 \(AC+ k CO\), \(DB+kDO\)를 최소화하는 점으로 잡으면 되고, 이 위치는 각 식의 대칭성에 의해서 원점을 기준으로 대칭임을 확인할 수 있다. 물론, \(AC+kCO\)가 유일한 \(C\)에 대해서 최솟값을 가진다는 사실을 확인해야 한다. 하지만 이 풀이는 \(C, D\)가 원점을 기준으로 같은 방향에 있을 경우를 처리하지 못하고, 이 경우를 처리하는 것이 생각보다 논리적으로 하기 까다롭다. 여기서 말리기 쉽다. 실제로 나도 여기서 한 번 말렸고, 1-(3)을 해결한 뒤에 돌아와서 풀 수 있었다. 

아이디어는 \(CD\)의 길이를 고정하고 생각하는 것이다. 그러면 \(AC+DB\)의 길이를 최소화하는 문제가 된다.

\(B\)를 \(CD\) 길이만큼 \(x\)축 방향으로 (\(C\)에 가까워지는 방향으로) 평행이동시킨 것을 \(B'\)이라 하자.

그러면 \(AC+CB'\)의 길이를 최소화하는 문제가 되고, 이는 다시 1-(1)처럼 \(B'\)을 \(x\)축 기준으로 대칭시켜서 풀 수 있는 문제가 된다. 이제 적당하게 계산을 해주면 원하는 결론이 얻어진다. 

\(D\)가 \(C\)보다 왼쪽에 있는 경우에 관해서 의문이 들 수 있는데, 이 풀이는 이 경우에도 정당하다.

1-(3)은 1-(2)의 결론에 의해 \(C(-u,0), D(u,0), u \ge 0\)을 잡고 (\(C\)가 \(D\)보다 왼쪽에 있어야 최소임은 자명하다) $$ f(u) = AC + k CD + DB = 2ku+2\sqrt{(10-u)^2+2^2} $$를 설정하자. 우리의 목표는 \(f(u)\)의 최솟값이 \(u=0\)에서 얻어지지 않는 \(k\)의 범위를 구하는 것이다. 

\(f\)를 한 번 미분하면, \(f'(u)=2\left(k - \frac{(10-u)}{\sqrt{(10-u)^2+2^2}} \right) \)가 나온다. 

여기서 확인해야 할 점은, \( \frac{(10-u)}{\sqrt{(10-u)^2+2^2}} \)가 \(u\)에 대해서 감소하는 함수라는 것이다. 

즉, \(f'(u)\)는 \(u\)에 대해서 증가하는 함수라는 사실을 확인할 수 있다. 이제 \(k\)에 대한 논의를 시작할 수 있다.

만약 \(f'(0) \ge 0\)이라면, \(f\)는 \(u\)에 대한 증가함수이다. 최솟값은 \(u=0\)에서 나온다. 

만약 \(f'(0) < 0\)이라면, \(f\)는 확실하게 \(u=0\)에서 최솟값을 가지지는 않는다. 

그러므로 커트는 \(f'(0)=0\)일 경우에 일어나며, 이 경우에서 \(k=\frac{5}{\sqrt{26}}\)이다. 

2번으로 넘어갔다. 상당히 새롭고 참신한 문제를 내려고 노력하신 것 같다. 정말 재밌는 문제.

우선 2-(1)을 풀기 위해, 우리가 무엇을 원하는 지를 다시 한 번 확인해보자. 

목표: \(|y|>x^2\)이면 \(0\)이 아닌 정수 \(m\)에 대해 \(|x^2+2my|>|y|>0\)이 성립함을 보이자.

좌변을 \(m\)에 대한 식으로 보면, 이 식은 \(-\frac{x^2}{2y}\)를 기점으로 증/감이 바뀌는 V 모양 함수다.

그러므로, \(m\)이 \(-\frac{x^2}{2y}\)에 가장 가까운 \(0\)이 아닌 정수인 경우에만 부등식을 확인해주면 된다. 

\(|y|>x^2\)이므로 \(\left| \frac{x^2}{2y} \right| \le \frac{1}{2}\)가 성립하고, 결국 \(m=\pm 1\)만 보면 충분하다. 

계산을 간단하기 위해서, 다음 보조정리들을 활용하도록 한다. 아래 논의에서 '부호'는 양수/0/음수로 나뉜다.

보조정리 1: \(0 \le |x|<|y|\)인 실수 \(x, y\)가 있다. \(y\)와 \(y+x\)와 \(y-x\)는 모두 부호가 동일하다. 

보조정리 2: \(x, y\)가 부호가 동일한 \(0\)이 아닌 실수라면, \(|x+y| > |y|\)가 성립한다. 

두 보조정리의 증명은 자명하므로 생략한다. 이제 \(m = \pm 1\)일 때 부등식을 증명해보자. 

\(m=1\)인 경우: \(y\)와 \(y+x^2\)의 부호가 동일하므로, \(|x^2+2y| = |y+(y+x^2)| > |y|\)다.

\(m=-1\)인 경우: \(y\)와 \(y-x^2\)의 부호가 동일하므로, \(|x^2-2y|=|y+(y-x^2)| > |y|\)다.

결국 \(m=\pm 1\)일 때 부등식이 성립하고, 모든 \(0\)이 아닌 정수 \(m\)에 대해 \(|x^2+2my|>|y|\)가 성립한다. 

한편, \(|y|>x^2 \ge 0\)이므로 \(|y|>0\)도 어렵지 않게 얻어진다. 이렇게 2-(1)의 증명이 끝난다. 

2-(2)는 답을 추측하는 게 중요한 문제다. 답은 되돌이점이 '아니다'. 

2-(1)에서와 마찬가지 방식의 논의로, \(T\)에 속한 점이 시행 \((P)\)를 통해서 \(S\)로 이동함을 알 수 있다.

\((1,0)\)에서 시행 \((Q)\)를 적용하면 \((1,2n)\)으로 이동하고, 이 점은 \(n\)이 \(0\)이 아닌 정수면 무조건 \(S\)에 속한다. 

그러므로 우리의 점은 \((P), (Q)\)를 반복 적용하면서 \(S, T\) 사이를 반복적으로 움직이게 된다. 

그러나 \((1,0)\)은 \(S\)에도, \(T\)에도 없다. 그러므로 \((1,0)\)으로 되돌아 오는 것은 불가능하다. 증명 끝.

면접

어마어마하게 떨었다. 면접에서는 풀이지를 교수님께 보여드리면서, 연필로 중요 내용을 짚어가며 설명하게 되었다.  

긴장한 상태에서 최대한 엄밀하게 모든 내용을 설명하려고 하다보니, 시간이 꽤 오래 걸렸다.   

교수님의 질문은 2-(2)에서의 '마찬가지 방식의 논의'에 대한 설명 요구였다. 이 설명을 마쳤더니 시간이 3분 남았다. 

그 후 교수님께서는 자소서 4번 - 독서에 관한 질문을 하셨고, (인상 깊게 읽은 책 소개) 전날에 준비한 덕분에 대답할 수 있었다. 

다음은 다른 친구들이 받았다던 추가질문 몇 개다. 

추가질문 1: 되돌이점의 예시를 하나 더 찾으시오. 

추가질문 2: https://en.wikipedia.org/wiki/Sharkovskii%27s_theorem의 하위호환 (이게 왜 나왔는지 잘 모르겠다)

periodic point of period \(3\)가 존재하면, periodic point of period \(2\)가 존재함을 보이는 문제가 나왔다고 한다.

물론 여기서 다루는 함수는 연속함수. 자세한 내용은 위키 링크를 타고 읽어보는 게 좋을 것 같다. 

3년간 고생이 많았는데 좋은 결과가 나왔으면 좋겠다. 

UPD: SNU 2019.

29.

기본 세팅을 다음과 같이 하자. $$\vec{AP} = p\vec{AB}$$ $$ \vec{AQ} = q\vec{AB} + (1-q) \vec{AC}$$ $$\vec{AR} = r \vec{AC}$$ 여기서 \(p, q, r\)은 모두 \(0\) 이상 \(1\) 이하의 실수이다. 

이제 계산하면 $$ \vec{AX} = \left( \frac{1}{4} p  + \frac{1}{2} q \right) \vec{AB} + \left( \frac{1}{4}r + \frac{1}{2} (1-q) \right) \vec{AC}$$이다. 여기서 \(\frac{1}{2}q \vec{AB} + \frac{1}{2}(1-q)\vec{AC}\)는 \(AB\)의 중점과 \(AC\)의 중점을 연결한 선분이 된다. 

이 선분 위에 있는 점 \(X'\)을 잡자. 그러면 

$$ \vec{AP} = \vec{AX'} + \frac{1}{4} p \vec{AB} + \frac{1}{4} r \vec{AC} $$가 가능한 \(P\)의 자취를 구하는 것이 목적이 된다. 

\(\frac{1}{4}p \vec{AB} + \frac{1}{4}q \vec{AC} \)를 더하는 것은 각 변이 \(AB, AC\)와 평행하고 길이가 \(\frac{1}{4}AB\), \(\frac{1}{4}AC\)인 평행사변형을 그리는 것이다. 

이제 \(\vec{AX}\)가 어떤 영역을 움직이는지 쉽게 파악할 수 있다. 답은 \(S=9 \cdot \left(1- \frac{1}{4} - 2 \cdot \frac{1}{16} \right) = \frac{45}{8}\)이므로 \(53\)이다.

30. 

\(g(x)\)를 미분하는 것으로 시작하자. 미분해보면, 결과는 $$ g'(x) = \frac{-f'(x) \cos f(x)}{(2+\sin f(x))^2} $$이 나온다. 이제 (가), (나) 조건을 통해서 필요한 정보를 얻어보자. 

(가) 조건에서는, \(\alpha_1 = 0\)을 알려준다. \(g'(0)=0\)이므로, \(f'(0)=0\)이거나 \(\cos f(0) = 0\)임을 알 수 있다. 

그런데 \(g(0)=\frac{2}{5}\)이므로 \(\sin f(0) = \frac{1}{2}\)이다. 여기서 \(\cos f(0)=0\)이 불가능하다는 것을 얻는다. 

한편, \( 0< f(0) < \frac{\pi}{2}\)이므로 \(f(0)=\frac{\pi}{6}\)이다. 그러므로 (가)에서 얻은 조건은 두 개로 요약 가능하다.

첫 번째 조건: \(f(0)=\frac{\pi}{6}\)이다. 두 번째 조건: \(f'(0)=0\)이다. 

구해야 하는 \(f\)의 계수 4개에 대한 일차식을 무려 3개를 얻었다. (최고차항 계수가 주어졌으므로.) 

(나) 조건에서는, 식을 살짝 바꿔주면 $$\sin f(\alpha_5) = \sin f(\alpha_2) + \frac{1}{2}$$를 얻는다. \(g'(x)\)의 형태에서, 우리는 임의의 극대/극소점 \(\alpha\)에 대해 다음이 성립함을 안다. 

팩트: \(f'(\alpha)=0\)이거나 \(\cos f(\alpha) = 0\) - 즉 \(\sin f(\alpha) = \pm 1\)이다. 

\(\sin f(\alpha_5) = \sin f(\alpha_2) + \frac{1}{2}\)라는 식을 관찰해보면, 두 \(\sin\) 값이 모두 \(\pm 1\) 형태일 수는 없다. 

또한, \(f'\)의 근은 최대 2개이므로, \(f'(\alpha_2) = f'(\alpha_5) = 0\)일 수는 없다.

그렇다면 결론은 하나다. 두 \(\alpha\) 중 하나는 \(f'\)이 \(0\)이 되고, 하나는 \(\sin f(\alpha)\)가 \(\pm 1\)이 된다. 

\(\sin\) 함숫값의 절댓값이 \(1\) 이하임에 착안하여 경우를 나누면, 다음 둘 중 하나임을 알 수 있다.

Case 1. \(\sin f(\alpha_2) = \frac{1}{2}\), \(\sin f(\alpha_5) = 1\), \(f'(\alpha_2) = 0\).

Case 2. \(\sin f(\alpha_2) = -1 \), \(\sin f(\alpha_5) = -\frac{1}{2}\), \(f'(\alpha_5) = 0\).

이제 두 경우에 따라서 각각 \(f\)가 알맞게 나오는 지 확인해보도록 하자. 

Case 1. \(\sin f(\alpha_2) = \frac{1}{2}\), \(\sin f(\alpha_5) = 1\), \(f'(\alpha_2) = 0\).

이 경우에는 \(g(\alpha_1) = g(0) = \frac{2}{5} = g(\alpha_2)\)가 된다. 

그러므로 \((\alpha_1, \alpha_2)\) 안에서 \(g(x)\)는 극대/극소를 적어도 한 번 가진다. 모순. 

Case 2. \(\sin f(\alpha_2) = -1\), \(\sin f(\alpha_5) = -\frac{1}{2}\), \(f'(\alpha_5)=0\).

이제 \(f'\)의 근은 \(0\)과 \(\alpha_5\)임이 확정되었다. 다른 근은 존재하지 않는다.

그러므로, \((0,\alpha_5)\)에서 \(\sin f(\alpha) = \pm 1\)인 모든 \(\alpha\)는 극대/극소점이다. 

이 점들은 \(f'(\alpha) \neq 0\)을 만족하므로, 그 점에서 \(\cos f(\alpha)\)의 부호가 변하기 때문이다.

또한, 극대/극소점 \(\alpha_2, \alpha_3, \alpha_4\)에서는 모두 \(\sin f(\alpha) = \pm 1\)이 된다. 

마지막으로, \(f\)는 구간 \([0,\alpha_5]\)에서 감소함이 확정되었다. 

그러므로 \(f(\alpha_2) = -\frac{\pi}{2}\), \(f(\alpha_3) = -\frac{3\pi}{2}\), \(f(\alpha_4) = -\frac{5\pi}{2}\)를 얻을 수 있다. 

이제 \(f(\alpha_5)\)를 구할 수 있다. \(\alpha_5 < -\frac{7\pi}{2}\)라면, \(-\frac{7\pi}{2}\) 역시 극대/극소점이 되므로 모순이다. 

그러므로 \(f(\alpha_5) \in (-\frac{7\pi}{2}, -\frac{5\pi}{2})\)이고, \(f(\alpha_5)= -\frac{17}{6} \pi\)를 얻을 수 있다. 

\(\alpha_5 = t\)라고 편의상 두자. 그러면 \(f'(x)=18\pi x(x-t)\)가 된다. 이를 적분하면, \(f(0)=\frac{\pi}{6}\)이므로 \(f(x)=6\pi x^3 - 9\pi t x^2 + \frac{\pi}{6}\)이 된다. 여기서 \(x=t\)를 대입하면, $$ 6t^3 - 9t^3 + \frac{1}{6} = -\frac{17}{6} $$를 얻는다. 그러므로 \(t=1\)이고, \(f(x) = 6\pi x^3 - 9\pi x^2 + \frac{\pi}{6}\)이다. 

이제 남은 것은 계산이다. \(f'\left(-\frac{1}{2}\right) = \frac{27\pi}{2}\)와, \(f\left(-\frac{1}{2}\right) = -\frac{17}{6}\pi\)를 얻는다.

그러면 $$ g'\left(-\frac{1}{2}\right) = \frac{-\frac{27\pi}{2} \cdot -\frac{\sqrt{3}}{2}}{ \left(2 - \frac{1}{2} \right)^2} = 3 \sqrt{3} \pi$$를 얻고, 답은 \((3\sqrt{3})^2 = 27\)이 된다. 

문제 (완벽하게 동일한 statement가 아닐 수 있음)

1 - (1) 다음의 조건을 만족하는 집합 \(A, B, C\)를 고르는 방법의 수는?

조건 1. \(A, B, C\)는 \( \{1,2,3,4,5,6\}\)의 부분집합으로, \( A \cup B \cup C = \{1,2,3,4,5,6\} \)이다.

조건 2. \( n( A \cap B) =2\)이고, \( n(A \cap C)=1\)이다. 

1 - (2) 다음의 조건을 만족하는 집합 \( D, E\)를 고르는 방법의 수는?

조건 1. \(D, E\)는 \( \{7,8,9\} \)의 부분집합으로, \( D \cup E = \{ 7, 8, 9 \} \)이다. 

조건 2. \( n(D) > n(E) \ge 1\)이다. 

2. 다음 조건을 만족하는 함수 \(f\)가 있으면 찾고, 없다면 없음을 보여라.

조건. \(f\)는 \([0,1]\)에서 연속이며, \(f(0)=1\)이다. 또한, 다음이 성립한다. 

$$ \int_0^1 f(x) dx = \int_0^1 xf(x) dx = \int_0^1 x^2f(x) dx = 0$$

________________________________________________________________________________________________________________________

풀이 및 후기

오전 맨 마지막으로 면접을 봤다. 기다리느라 너무 지루했고 피곤했다. 컨디션 떡락 ㅠㅠ

조금 떨린 상태로 문제지를 열었다. 1번은 무난해 보이고, 2번이 변별력이 있어 보였다. 

2번을 읽는데... 이거 완전 https://en.wikipedia.org/wiki/Gram%E2%80%93Schmidt_process 아니냐???

(추가설명) 이걸 알면 삼차함수로 답을 구할 수 있다는 것이 자명해진다. \( 1, x, x^2, x^3\)으로 그램슈미츠 돌리면 답이 나오니까.

아니면 이거 완전 https://en.wikipedia.org/wiki/Legendre_polynomials 아니냐???

(추가설명) 이걸 알면 문제의 답을 아는 것과 마찬가지다. \(P_3(x)\)를 적당히 평행이동/상수배하면 된다.

결국 \( f(x)=x^3+ax^2+bx+c\)를 잡아주고, 적분값이 모두 \(0\)이 되도록 하는 \(a, b, c\)를 계산했다.

이를 계산하는 것은 그냥 연립일차방정식을 세워서 풀어주면 된다. 더럽지만 어쩔 수 없음. 

실제로 식을 세워주면, 다음 세 식을 어렵지 않게 얻을 수 있다. 

$$ \frac{1}{4} + \frac{a}{3} + \frac{b}{2} + c = 0 $$

$$ \frac{1}{5} + \frac{a}{4} + \frac{b}{3} + \frac{c}{2} = 0 $$

$$ \frac{1}{6} + \frac{a}{5} + \frac{b}{4} + \frac{c}{3} = 0 $$ 

\(a, b, c\)가 계산되면, \(f(0)=1\)을 만족하도록 상수배를 해주기만 하면 된다. 이 부분 계산은 생략. 

그렇게 하면 \(f(x)=-20x^3+30x^2-12x+1\)일 경우 주어진 조건이 모두 만족됨을 알 수 있다. 여기까지 7분 소요.

기분이 좋은 상태로 1번을 잡았고, 실제로도 무난한 확통 문제임을 알 수 있었다. 

1-(1)은 \( n(A \cap B \cap C)\)에 대하여 경우를 나눠서 해결할 수 있다. 벤 다이어그램을 그리는 것이 도움이 된다. 

만약 \( n (A \cap B \cap C) = 1\)이라면, 다음이 만족되어야 한다. 

1. \( A \cap B \cap C\)에는 원소가 하나 있어야 함.

2. \( A \cap B \cap C^C\)에는 원소가 하나 있어야 함.

3. \( A \cap B^C \cap C\)에는 원소가 없어야 함.

4. 나머지 원소들은 \( A \cap (B \cup C)^C\), \(B \cap (C \cup A)^C\), \(C \cap (A \cup B)^C\), 또는 \( B \cap C \cap A^C\)에 속해야 함.

1에 해당하는 원소 고르는 게 \(6\)가지, 2에 해당하는 원소 고르는 게 \(5\)가지, 4에서 배치하는 게 \(4^4\)가지. 총 \(7680\)개.

만약 \( n (A \cap B \cap C) = 0 \)이라면, 다음이 만족되어야 한다. 

1. \( A \cap B \cap C\)에는 원소가 없어야 함.

2. \( A \cap B \cap C^C\)에는 원소가 두 개 있어야 함.

3. \( A \cap B^C \cap C\)에는 원소가 한 개 있어야 함.

4. 나머지 원소들은 \( A \cap (B \cup C)^C\), \(B \cap (C \cup A)^C\), \(C \cap (A \cup B)^C\), 또는 \( B \cap C \cap A^C\)에 속해야 함.

2에 해당하는 원소들 고르는 게 \(\binom{6}{2}=15\)가지, 3에 해당하는 원소 고르는 게 \(4\)가지, 4에서 배치하는 게 \(4^3\)가지. 총 \(3840\)개.

이 둘을 합치면 답은 \(7680 + 3840 = 11520\)임을 알 수 있다. 

1-(2)는 \(n(D)\)에 관해 경우를 나눠서 쉽게 풀 수 있다. 

\(n(D)\)가 3이면, \(D\)는 유일하게 결정되고 \(E\)는 크기가 1 또는 2인 부분집합이면 되니까 총 6가지 경우가 나온다.

\(n(D)\)가 2면, \(E\)는 크기가 1인 집합이고 \(D \cup E = \{7,8,9\} \)가 성립하니 \(D\)만 결정하면 \(E\)가 자동 결정되어 총 3가지.  

그래서 이 둘을 합치면 답은 \(6+3=9\)임을 알 수 있다. 여기까지 13분 소요. 나머지 7분은 검산했다. 

발표는 작년처럼 종이 주고 여기에 풀이를 적고 보여주면서 설명하라고 하셨다. 

함수 \(f\)의 형태를 보여주거나, 벤 다이어그램을 그려서 보여주는 용도로 적당히 사용했다.

시간이 좀 남아서 2번에 대한 추가설명으로 Gram-Schmidt 직교화에 대하여 가볍게 언급했다. 

총평하자면 1번은 쉽고, 2번은 어려웠다. 분위기를 보니 수학과 지원하는 친구들이 2번을 꽤 푼 것 같다. 

2번 문제는 연대가 좋아하는 스타일의 함수 찾기 문제였고, 특히 수학에 대한 직관이 뛰어난 친구들이 잘 풀 것 같다. 

문제

다음 식을 만족하는 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\)