Let \(A_1,A_2,\ldots,A_n\) be subsets of \(\{1,2,\ldots,n\}\) such that \(i\notin A_i\) for all \(i\). Prove that there exist four sets \(C_1,C_2,C_3,C_4\) such that \(C_1\cup C_2\cup C_3\cup C_4=\{1,2,\ldots,n\} \) and for all \(i\) and \(j\), if \(i\in C_j\), then \( \lvert A_i\cap C_j\rvert \le \frac12 \lvert A_i\rvert\).
Let \( G \) be a subgroup of \( GL_2 (\mathbb{R}) \) generated by \( \begin{pmatrix} 2 & 0 \\ 0 & 1 \end{pmatrix} \) and \( \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} \). Let \( H \) be a subset of \( G \) that consists of all matrices in \( G \) whose diagonal entries are \( 1 \). Prove that \( H \) is a subgroup of \( G \) but not finitely generated.
The best solution was submitted by Jo, Tae Hyouk (조태혁, 수리과학과 2014학번). Congratulations!
Here is his solution of problem 2016-3.
Alternative solutions were submitted by 강한필 (2016학번, +3), 국윤범 (수리과학과 2015학번, +3), 김경석 (연세대학교 의예과 2016학번, +3), 김기택 (수리과학과 2015학번, +3), 김동규 (수리과학과 2015학번, +3), 김동률 (수리과학과 2015학번, +3), 송교범 (서대전고등학교 3학년, +3), 어수강 (서울대학교 수학교육과 박사과정, +3), 유찬진 (수리과학과 2015학번, +3), 이시우 (포항공대 수학과 2013학번, +3), 이정환 (수리과학과 2015학번, +3), 이종원 (수리과학과 2014학번, +3), 이준호 (2016학번, +3), 이태영 (2013학번, +3), 장기정 (수리과학과 2014학번, +3), 최대범 (2016학번, +3), Muhammaadfiruz Hasanov (2014학번, +3), 배형진 (마포고등학교 2학년, +2), 이상민 (수리과학과 2014학번, +2).
Let \(T\) be a tree on \(n\) vertices \(V=\{1,2,\ldots,n\}\). For two vertices \(i\) and \(j\), let \(d_{ij}\) be the distance between \(i\) and \(j\), that is the number of edges in the unique path from \(i\) to \(j\). Let \(D_T(x)=(x^{d_{ij}})_{i,j\in V}\) be the \(n\times n\) matrix. Prove that \[ \det (D_T(x))=(1-x^2)^{n-1}.\]
For \( a \geq 0 \), find
\[
\lim_{n \to \infty} n \int_{-1}^0 \left( x + \frac{x^2}{2} + e^{ax} \right)^n dx.
\]
The best solution was submitted by Jang, Kijoung (장기정, 수리과학과 2014학번). Congratulations!
Here is his solution of problem 2016-02.
Alternative solutions were submitted by 국윤범 (수리과학과 2015학번, +3), 김동규 (수리과학과 2015학번, +3), 김동하 (기계공학과 2014학번, +3), 이상민 (수리과학과 2014학번, +3), 이시우 (포항공대 수학과 2013학번, +3), 이종원 (수리과학과 2014학번, +3), 정성진 (수리과학과 2013학번, +3), 최대범 (2016학번, +3), 최인혁 (물리학과 2015학번, +3), Muhammaadfiruz Hasanov (2014학번, +3), 이준호 (2016학번, +2). One incorrect solution was submitted.
Prove that for every \( x_1, x_2,\ldots,x_n\in [0,1]\), there exist \(\varepsilon_1,\varepsilon_2,\ldots,\varepsilon_n\in\{1/2,-1/2\}\) such that for all \(k=1,2,\ldots,n-1\), \[ \left\lvert \sum_{i=1}^k \varepsilon_i x_i-\sum_{i=k+1}^n \varepsilon_i x_i \right\rvert\le 1.\]
The best solution was submitted by Lee, Jongwon (이종원, 수리과학과 2014학번). Congratulations!
Here is his solution of problem 2016-1.
Alternative solutions were submitted by 노희광 (화학과 2014학번, +2), 안현수 (2016학번, +2), 이상민 (수리과학과 2014학번, +2), 홍혁표 (수리과학과 2013학번, +2). There were 10 incorrect submissions.
Let \( G \) be a subgroup of \( GL_2 (\mathbb{R}) \) generated by \( \begin{pmatrix} 2 & 0 \\ 0 & 1 \end{pmatrix} \) and \( \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} \). Let \( H \) be a subset of \( G \) that consists of all matrices in \( G \) whose diagonal entries are \( 1 \). Prove that \( H \) is a subgroup of \( G \) but not finitely generated.
There were 13 submissions for problem 2016-1 but no correct solutions were submitted so far.
For \( a \geq 0 \), find
\[
\lim_{n \to \infty} n \int_{-1}^0 \left( x + \frac{x^2}{2} + e^{ax} \right)^n dx.
\]
Prove that for every \( x_1, x_2,\ldots,x_n\in [0,1]\), there exist \(\varepsilon_1,\varepsilon_2,\ldots,\varepsilon_n\in\{1/2,-1/2\}\) such that for all \(k=1,2,\ldots,n-1\), \[ \left\lvert \sum_{i=1}^k \varepsilon_i x_i-\sum_{i=k+1}^n \varepsilon_i x_i \right\rvert\le 1.\]
Thanks all for participating POW actively. Here’s the list of winners:
1st prize (Gold): Lee, Jongwon (이종원), 수리과학과 2014학번.
2nd prize (Silver): Park, Sunghyuk (박성혁), 수리과학과 2014학번.
3rd prize (Bronze): Shin, Joonhyung (신준형), 2015학번.
3rd prize (Bronze): Jang, Kijoung (장기정), 수리과학과 2014학번.
3rd prize (Bronze): Choi, Inhyeok (최인혁), 2015학번.
이종원 (수리과학과 2014학번) 37점, 박성혁 (수리과학과 2014학번) 36점, 신준형 (2015학번) 33점, 장기정 (수리과학과 2014학번) 32점, 최인혁 (2015학번) 32점, 이영민 (수리과학과 2012학번) 18점, 박훈민 (수리과학과 2013학번) 17점, 김동률 (2015학번) 10점, 이상민 (수리과학과 2014학번) 8점, 김재준 (2014학번) 6점, 이정환 (2015학번) 6점, 오동우 (2015학번) 5점, 유찬진 (2015학번) 5점, 함도규 (2015학번) 5점, 이신영 (물리학과 2012학번) 4점, 김경석 (2015학번) 3점, 김기택 (2015학번) 3점, 김희주 (2015학번) 2점, 이호일 (수리과학과 2013학번) 2점, 이경훈 (수리과학과 2014학번) 1점.