rkm0959

Starrysky와 함께한 문제 풀이 세션. 4문제 3시간으로 진행했다. 

1. 111개의 동전이 \(n \times n\) 체스판 위에 놓여있다. 체스판의 한 cell은 동전을 0개 이상 가지고 있다. 또한, 공통 변을 가지는 인접한 두 cell이 갖는 동전의 개수의 차이는 정확하게 1이다. 이러한 동전의 배치가 가능한 최대의 \(n\)을 구하시오. 

2. \(f: \mathbb{R} \rightarrow \mathbb{R}\)는 연속함수이다. \(x\)가 shadow point라는 것은, \(y>x\)이며 \(f(y)>f(x)\)인 \(y\)가 존재한다는 것이다. 두 실수 \(a, b\)가 존재하여 \(a<b\)이고 \((a,b)\)에 속한 모든 점은 shadow point이며 \(a, b\) 각각은 shadow point가 아니라 하자.

(a) 이때, \(x \in (a,b)\)이면 \(f(x) \le f(b)\)임을 보여라.

(b) 또한, \(f(a)=f(b)\)도 성립함을 보여라.

3. \(P\)는 \(\{1,2, \cdots n\}\)의 부분집합들의 nonempty collection으로, 다음 조건을 만족한다.

(1) \(S, S' \in P\)가 성립하면 \(S \cup S' \in P\)이고, \(S \cap S' \in P\)이다.

(2) \(S \in P\)이고 \(S \neq \emptyset\)이면 어떤 \(T \in P\)가 있어 \(T \subset S\)이고 \(|T|=|S|-1\)이다.

이제 어떤 함수 \(f: P \rightarrow \mathbb{R}\)이 있어 \(f(\emptyset)=0\)이고 모든 \(S, S' \in P\)에 대하여 $$ f(S \cup S') = f(S) + f(S') - f(S \cap S')$$이 성립한다고 가정하자. 그렇다면, 적당한 실수 \(f_1, f_2, \cdots f_n\)를 설정하여 $$ f(S) = \sum_{i \in S} f_i $$가 모든 집합 \(S \in P\)에 대하여 성립하도록 할 수 있는가?

4. \(a_1, a_2, \cdots \)는 모두 실수이다. 적당한 상수 \(A\)가 있어 $$ \int_{-\infty}^\infty \left( \sum_{i=1}^n \frac{1}{1+(x-a_i)^2} \right)^2 dx \le An$$이 모든 \(n\)에 대해 성립한다고 하자. 다음 부등식이 모든 \(n\)에 대해서 성립하도록 하는 상수 \(B>0\)이 존재함을 증명하시오. $$ \sum_{i,j=1}^n (1+(a_i-a_j)^2) \ge Bn^3 $$ Bonus. 또한, 우변을 \(Bn^3\) 대신 \(Bn^4\)으로 바꿔도 같은 명제가 성립함을 보여라.

______________________________________________________________________________________________________________________

________________________________________________________________________________________________________________________

풀이를 빡빡하게 서술하지는 않고, 문제를 접근한 방법과 간단한 풀이의 sketch를 적는다.

1.

2. 

3. 

다른 풀이도 하나 소개한다. 이 풀이를 위한 핵심 관찰도 문제를 풀면서 하긴 했는데, 이걸 풀이로 발전시키진 못했다.

4. 

이 문제도 다른 풀이를 하나 소개한다. 진짜 멋진 풀이라고 생각한다. 위의 풀이보다 훨씬 더 깔끔한 듯.

문제 다운로드 링크

이 포스팅에서는 수학 분야 2019년 선발 문제 M2, M3, M4, M5를 푼다.

스포 방지선

___________________________________________________________________________________________________

_____________________________________________________________________________________________________

M2

두 \(n \times n\) 행렬 \(A, B\)에 대하여 \(d(A,B) = \text{max}_{1 \le i, j \le n} |A_{i,j}-B_{i,j}|\)라 하자.

\(I_n\)으로 수렴하는 모든 행렬의 수열은 \(I_n\)을 포함하므로, 다음 명제를 증명할 수 있다.

Claim: 적당한 양의 실수 \(\epsilon\)이 존재하여, 모든 \(M (\neq I_n) \in G\)에 대해 \(d(M,I_n)>\epsilon\)이다.

Proof of Claim: 귀류법을 사용하면, 모든 \(\epsilon>0\)에 대하여 \(M (\neq I_n) \in G\)가 존재하여 \(d(M,I_n)<\epsilon\)이다. 

\(\epsilon = \frac{1}{n}\)에 대하여 얻어지는 \(M_n\)을 모아서 수열로 만들면, 그 수열은 \(I_n\)에 수렴하지만 \(I_n\)을 포함하지 않는다. 이는 모순이다.

Claim을 통해서 얻어지는 "적당한 양의 실수 \(\epsilon\)"을 \(\epsilon_0\)라고 하자.

본 문제도 귀류법으로 증명하자. 모든 entry가 \([-A,A]\)에 속하는 \(M \in G\)가 무한히 많다고 가정하자.

그렇다면 임의의 \(\epsilon>0\)에 대해서 두 행렬 \(M, N \in G\)이 있어 모든 entry가 \([-A,A]\)에 속하고, \(d(M,N)<\epsilon\)이다. 

이는 hypercube \([-A,A]^{n^2}\)을 각 변의 길이가 \(\epsilon\)인 hypercube로 분할한 뒤, 비둘기집의 원리를 적용하면 증명할 수 있다. 

\(\epsilon>0\)를 하나 잡자. 정확한 \(\epsilon\)의 값은 나중에 정하도록 한다.

모든 entry가 \([-A,A]\)에 속하고 \(G\)에 속하며, \(d(M,N)<\epsilon\)인 두 행렬 \(M, N\)을 잡자.

\(N^* = M^{-1}N\)이라 하자. \(\vec{m_i}\)를 \(M\)의 \(i\)번째 row vector라고 하고, \(\vec{r_j}\)를 \(N^*-I_n\)의 \(j\)번째 column vector라고 하자.

그러면 \(N-M=M(N^*-I_n)\)이므로, \(N-M\)의 각 entry는 \(\vec{m_i} \cdot \vec{r_j}\)라고 쓸 수 있다.

\(M, N\)의 설정에 의해 \(d(M,N)<\epsilon\)이고, 이는 모든 \(i, j\)에 대해 \(|\vec{m_i} \cdot \vec{r_j}| < \epsilon\)을 의미한다.

한편, \(N^* \in G\)이므로 \(d(N^*, I_n) > \epsilon_0\)이다. 이는 적당한 \(1 \le t \le n\)에 대하여 \( |\vec{r_t}| > \epsilon_0\)임을 의미한다. 

여기서 모순을 얻을 수 있다. \(\vec{v_1} = \frac{\vec{r_t}}{|\vec{r_t}|}\)라 하고, 확장하여 \(\vec{v_1}, \vec{v_2}, \cdots \vec{v_n}\)이 \(\mathbb{R}^n\)의 orthonormal basis가 되도록 하자.

각 \(\vec{m_i}\)를 \(\vec{m_i} = c_{i,1}\vec{v_1} + c_{i,2}\vec{v_2}+ \cdots + c_{i,n} \vec{v_n}\)라고 표현할 수 있다.

조건에 의해 \(det(M)=1\)이므로, \(c_{i,j}\)를 entry로 가지는 행렬 \(C\) 역시 determinant가 \(\pm 1\)이다.

한편, 모든 \(i, j\)에 대하여 \( |c_{i,j}| = |m_i \cdot v_j| \le |m_i| \le An\)이다. 

만약 모든 \(i\)에 대하여 \( |c_{i,1}| \le \frac{1}{A^{n-1} \cdot n^n \cdot n!}\)이라면, 행렬식의 정의에서 $$ |det(C)| \le n! \cdot \frac{1}{A^{n-1} \cdot n^n \cdot n!} \cdot (An)^{n-1} < 1$$일 것이다. 그러므로 \(|c_{l,1}| > \frac{1}{A^{n-1} \cdot n^n \cdot n!}\)인 \(1 \le l \le n\)이 있다.

\(T=\frac{1}{A^{n-1}\cdot n^n \cdot n!}\)이라 하자. \(|\vec{m_l} \cdot \vec{v_1}| = |c_{l,1}| > T\)이므로, \(|\vec{m_l} \cdot \vec{r_t}| > T \cdot |\vec{r_t}| > T\epsilon_0\)이다.

이제 \(\epsilon < \frac{1}{2} T\epsilon_0\)인 \(\epsilon>0\)을 잡으면, \(T\epsilon_0<|\vec{m_l} \cdot \vec{r_t}| < \epsilon < \frac{1}{2}T\epsilon_0\)이므로 모순이다. 증명 끝.

M3

(a) 다양한 풀이가 있지만 여기서는 확률적인 접근을 활용한다.

\(n\)개의 i.i.d. 확률변수 \(X_1, X_2, \cdots X_n \sim \text{unif}[0,1]\)이 있다고 하자.

여기서 \(X = \frac{X^2_1+X^2_2+\cdots X^2_n}{n}\)이라 하면, \(E(X)=\frac{1}{3}\)이고, \(Var(X)=\frac{4}{45n}\)임을 계산할 수 있다.

이제 Chebyshev의 부등식에 의해서, 모든 양수 \(k\)에 대해 \( P(|X-\frac{1}{3}| < \sqrt{\frac{4}{45n}} \cdot k ) \ge 1-\frac{1}{k^2}\)이다.

\(k=n^{1/4}\)를 택하면, \(P(|X-\frac{1}{3}| < \sqrt{ \frac{4}{45}} \cdot n^{-1/4}) \ge 1 - \frac{1}{\sqrt{n}}\)이다.

문제에서 원하는 값은 \(E(X^d)\)이다. 여기서 \(0 \le X^d \le 1\)임을 이용하자. 두 부등식

$$ E(X^d) \ge P \left(X > \frac{1}{3} - \sqrt{\frac{4}{45}} \cdot n^{-1/4} \right) \cdot \left(\frac{1}{3} - \sqrt{\frac{4}{45}} \cdot n^{-1/4} \right)^d \ge \left(1-\frac{1}{\sqrt{n}}\right) \cdot \left(\frac{1}{3} - \sqrt{\frac{4}{45}} \cdot n^{-1/4} \right)^d  $$ $$ E(X^d) \le \left(\frac{1}{3} + \sqrt{\frac{4}{45}} \cdot n^{-1/4} \right)^d + P \left(X>\frac{1}{3} + \sqrt{\frac{4}{45}} \cdot n^{-1/4} \right) \cdot 1^d \le \left(\frac{1}{3} + \sqrt{\frac{4}{45}} \cdot n^{-1/4} \right)^d + \frac{1}{\sqrt{n}} $$을 얻을 수 있고, 여기에 Squeeze 정리를 사용하면 \(n \rightarrow \infty\)에서 \(E(X^d) = 3^{-d}\)임을 얻을 수 있다.

(b) Taylor 전개를 사용하고, absolute convergence를 갖고 있으니 sum과 integral의 순서를 바꿔줄 수 있다.

그 후 (a)를 활용해주면, 결과는 \(\sum_{n=0}^\infty \frac{(-1)^n}{(2n)!} \left(\frac{\pi}{3} \right)^{2n} = \cos \frac{\pi}{3} = \frac{1}{2} \)임을 어렵지 않게 얻을 수 있다.

M4

(a) 답은 \(2^n\)이고, 등호는 \(t_i = 2^i\)인 경우에 성립한다.

\(S\)를 \(a_r>0\)인 \(r\)의 집합이라고 하면, \(|S| \le 2^n\)이며 \(\sum_{r \in S} a_r = 2^n\)이다.

그러므로 \(\sum_{r \in S} a^2_r = \frac{ \left( \sum_{r \in S} a_r \right)^2}{|S|} = \frac{2^{2n}}{|S|} \ge 2^n\)이다.

(b) 답은 \(\binom{2n}{n}\)이고, 등호는 \(t_1=t_2=\cdots = t_n=1\)인 경우에 성립한다.

\(s=\sum_{i=1}^n t_i\)라 하면 \(a_r= a_{s-r}\)이다. 그러므로 \(\sum_{r} a^2_r = \sum_{r} a_r a_{s-r}\)이다.

\(t_{n+i}=t_i\), \(1 \le i \le n\)이라고 하자. 그러면 이 값은 결국 \(s\)를 \(t_1, t_2, \cdots t_{2n}\)의 합으로 표현하는 방법의 수이다. 

두 집합 \(X, Y\)가 \(\sum_{i \in X} t_i = \sum_{j \in Y} t_j = s\)라 하면, \(X, Y\)는 서로를 포함하고 있지 않다.

즉, \(X \subset Y\)거나 \(Y \subset X\)일 수 없다. 이제 Sperner's Theorem을 끼얹으면 주어진 값이 최대 \(\binom{2n}{n}\)임을 알 수 있다.

M5

답은 \(a=4k+2\)일 때 \(-1\), 그렇지 않을 때 \(1\)이다.

Case 1. \(a\) 홀수

이 경우에는 \(p=a^2+b^2 \equiv 1 \pmod{4}\)이고, 이차상호법칙에 의해 $$ \left( \frac{a}{p} \right) = \left( \frac{p}{a} \right) = \left(\frac{a^2+b^2}{a}\right)=\left(\frac{b^2}{a}\right) = 1$$

Case 2. \(a=4k+2\)

이 경우에는 \(p=a^2+b^2 \equiv 5 \pmod{8}\)이다. \(a=2m\), \(m\)은 홀수라 하면, $$ \left(\frac{a}{p}\right) = \left(\frac{2}{p}\right) \cdot \left(\frac{m}{p}\right) = (-1)^{\frac{p^2-1}{8}} \cdot \left(\frac{p}{m}\right) = -\left(\frac{4m^2+b^2}{m}\right) = -\left(\frac{b^2}{m}\right) = -1$$

Case 3. \(a \equiv 0 \pmod{4}\)

이 경우에는 \(p = a^2+b^2 \equiv 1 \pmod{8}\)이다. \(a=2^km\), \(m\)은 홀수라 하면, $$ \left(\frac{a}{p}\right) = \left(\frac{2}{p}\right)^k \cdot \left(\frac{m}{p}\right) = (-1)^{\frac{p^2-1}{8} \cdot k} \cdot \left(\frac{p}{m}\right) = \left(\frac{2^{2k}m^2+b^2}{m}\right) = \left(\frac{b^2}{m}\right) = 1$$

세 Case를 모두 합치면 증명이 끝난다.