rkm0959

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\)

문제

(Graham, Pollak 1972) Prove that the edge set of \(K_n\) cannot be partitioned into the edge-disjoint union of less than \(n-1\) complete bipartite subgraphs. Also, prove that this bound is tight.

스포 방지선

________________________________________________________________________________________________________________________

________________________________________________________________________________________________________________________

(증명) \(K_n\)의 각 정점을 \(1, 2, \cdots , n\)이라 하자. 우선 \(n-1\)개의 완전 이분 그래프로 \(K_n\)을 분할하는 것은 쉽다. 

귀류법으로, 완전 이분 그래프 \(B_1 , B_2, \cdots B_m \)이 \(K_n\)을 분할한다고 하자. (단, \(m \le n-2\)다.)

또한, 각 완전 이분 그래프 \(B_k\) 안에서 두 disjoint independent set을 \(L_k, R_k\)라고 부르자.

즉, \(B_k\)의 간선은 \(L_k\)의 정점과 \(R_k\)의 정점 사이를 모두 연결한 것이다.

다음 조건을 만족하도록 \(K_n\)의 정점 \(v\)에 실수 \(x_v\)를 놓자. 

조건 1: 모든 \(1 \le k \le m\)에 대하여, \( \displaystyle \sum_{v \in L_k} x_v = 0 \)이고, \(\displaystyle \sum_{v=1}^n x_v = 0\) 

조건 2: \(\displaystyle \sum_{v=1}^n x^2_v \neq 0 \)이다. 즉, 모든 \(v\)에 대해 \(x_v\)가 전부 \(0\)은 아니다.

이것이 가능함을 보이자. 기초적인 선형대수학을 알면 쉽게 보일 수 있다.

조건 1은 식의 개수가 \(m+1\)개인 하나의 Homogeneous한 연립방정식을 이룬다. 

변수의 개수가 \(n\)개이고 \(m+1 < n\)이므로, 이 연립방정식은 non-trivial 해를 가진다. 

그러므로 조건 1, 2를 만족하도록 정점 \(v\)에 실수 \(x_v\)를 놓을 수 있다. 

이제 \(B_1 , B_2, \cdots B_m \)이 \(K_n\)의 edge set을 완벽하게 분할하므로, 다음 식이 성립한다.

$$ \sum_{1 \le i < j \le n} x_ix_j = \sum_{k=1}^m \left(\displaystyle \sum_{i \in L_k} x_i \right) \cdot  \left(\displaystyle \sum_{j \in R_k} x_j \right) $$

문제

\( 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 \)