For \(k,n\geq 1\), let \(v_1,\dots, v_n\) be unit vectors in \(\mathbb{R}^k\). Prove that we can always choose signs \(\varepsilon_1,\dots,\varepsilon_n\in \{-1, +1\}\) such that \(|\sum_{i=1}^{n} \varepsilon_i v_i |\leq \sqrt{n} \).

The best solution was submitted by 조유리 (문현여고 3학년, +4). Congratulations!

Here is the best solution of problem 2022-03.

Other solutions were submitted by 김예곤 (KAIST 수리과학과 19학번, +3), 구재현 (KAIST 전산학부 17학번, +3), 이명규 (KAIST 전산학부 20학번, +3), 문강연 (KAIST 새내기과정학부 22학번, +3), 박기찬 (KAIST 새내기과정학부 22학번, +3), 이호빈 (KAIST 수리과학과 대학원생, +3), 김기수 (KAIST 수리과학과 18학번, +3), 윤창기 (서울대학교 수리과학부 19학번, +3), 권민재 (KAIST 수리과학과 19학번, +3), 유태윤 (KAIST 수리과학과 20학번, +3), 하석민 (KAIST 수리과학과 17학번, +3), 박현영 (KAIST 전자및전자공학부 대학원생, +3), 강한필 (KAIST 전산학부 16학번, +3), 여인영 (KAIST 물리학과 20학번, +2). Late solutions were not graded.

Evaluate the following:

\[ \frac{1}{1^2 \cdot 3^3 \cdot 5^2} – \frac{1}{3^2 \cdot 5^3 \cdot 7^2} + \frac{1}{5^2 \cdot 7^3 \cdot 9^2} – \dots
\]

The best solution was submitted by 여인영 (KAIST 물리학과 20학번, +4). Congratulations!

Here is the best solution of problem 2022-01.

Other solutions were submitted by 조유리 (문현여고 3학년, +3), 김건우 (KAIST 수리과학과 17학번, +3), 김예곤 (KAIST 수리과학과 19학번, +3), 신민서 (KAIST 수리과학과 20학번, +3), 이명규 (KAIST 전산학부 20학번, +3), 조한슬 (KAIST 김재철AI대학원 대학원생, +3), 양준혁 (KAIST 수리과학과 20학번, +3), 박기찬 (KAIST 새내기과정학부 22학번, +3), 구은한 (KAIST 수리과학과 19학번, +3), 이호빈 (KAIST 수리과학과 대학원생, +3), 김기수 (KAIST 수리과학과 18학번, +3), 이종민 (KAIST 물리학과 21학번, +2). Late solutions were not graded.

There are \(n\) people participating to a chess tournament and every two players play one game. There are no draws. Let \(a_i\) be the number of wins of the \(i\)-th player and \(b_i\) be the number of losses of the \(i\)-th player. Prove that
\[\sum_{i\in [n]} a_i^2 = \sum_{i\in [n]} b_i^2.\]

The best solution was submitted by 구재현 (전산학부 2017학번, +4). Congratulations!

Here is the best solution of problem 2021-24.

Other solutions were submitted by 이도현 (수리과학과 2018학번, +3), 이재욱 (전기및전자공학부 2018학번, +3), 이충명 (기계공학과 대학원생, +3), 이호빈 (수리과학과 대학원생, +3), 전해구 (기계공학과 졸업생, +3). Late solutions were not graded.

Let \(F\) be a family of nonempty subsets of \([n]=\{1,\dots,n\}\) such that no two disjoint subsets of \(F\) have the same union. In other words, for \(F =\{ A_1,A_2,\dots, A_k\},\) there exists no two sets \(I, J\subseteq [k]\) with \(I\cap J =\emptyset\) and \(\bigcup_{i\in I}A_i = \bigcup_{j\in J} A_j\). Determine the maximum possible size of \(F\).

For the new version of POW 2021-21, the best solution was submitted by 이재욱 (전기및전자공학부 2018학번, +4). Congratulations!

Here is the best solution of problem 2021-21.

Determine all rational numbers that can be written as
\[
\frac{1}{n_1} + \frac{1}{n_1 n_2} + \frac{1}{n_1 n_2 n_3} + \dots + \frac{1}{n_1 n_2 n_3 \dots n_k} ,
\]
where \( n_1, n_2, n_3 \dots, n_k \) are positive integers greater than \(1\).

The best solution was submitted by 조정휘 (수리과학과 대학원생, +4). Congratulations!

Here is the best solution of problem 2021-22.

Other solutions were submitted by 신주홍 (수리과학과 2020학번, +3), 이재욱 (전기및전자공학부 2018학번, +3), 이호빈 (수리과학과 대학원생, +3), 전해구 (기계공학과 졸업생, +3).

Let \(F\) be a family of nonempty subsets of \([n]=\{1,\dots,n\}\) such that no two disjoint subsets of \(F\) have the same union. Determine the maximum possible size of \(F\).

The best solution was submitted by 전해구 (기계공학과 졸업생, +4). Congratulations!

Here is the best solution of problem 2021-21.

Say a natural number \(n\) is a cyclically perfect if one can arrange the numbers from 1 to \(n\) on the circle without a repeat so that the sum of any two consecutive numbers is a perfect square. Show that 32 is the smallest cyclically perfect number. Find the second smallest cyclically perfect number.

The best solution was submitted by 전해구 (기계공학과 졸업생, +4). Congratulations!

Here is the best solution of problem 2021-20.

Suppose that \( a_1 + a_2 + \dots + a_n =0 \) for real numbers \( a_1, a_2, \dots, a_n \) and \( n \geq 2\). Set \( a_{n+i}=a_i \) for \( i=1, 2, \dots \). Prove that
\[
\sum_{i=1}^n \frac{1}{a_i (a_i+a_{i+1}) (a_i+a_{i+1}+a_{i+2}) \dots (a_i+a_{i+1}+\dots+a_{i+n-2})} =0
\]
if the denominators are nonzero.

The best solution was submitted by 이도현 (수리과학과 2018학번, +4). Congratulations!

Here is the best solution of problem 2021-19.

Let \(T\) be a tree (an acyclic connected graph) on the vertex set \([n]=\{1,\dots, n\}\).
Let \(A\) be the adjacency matrix of \(T\), i.e., the \(n\times n\) matrix with \(A_{ij} = 1\) if \(i\) and \(j\) are adjacent in \(T\) and \(A_{ij}=0\) otherwise. Prove that the number of nonnegative eigenvalues of \(A\) equals to the size of the largest independent set of \(T\). Here, an independent set is a set of vertices where no two vertices in the set are adjacent.

The best solution was submitted by 전해구 (기계공학과 졸업생, +4). Congratulations!

Here is the best solution of problem 2021-18.

For a given positive integer \( n \) and a real number \( a \), find the maximum constant \( b \) such that
\[
x_1^n + x_2^n + \dots + x_n^n + a x_1 x_2 \dots x_n \geq b (x_1 + x_2 + \dots + x_n)^n
\]
for any non-negative \( x_1, x_2, \dots, x_n \).

The best solution was submitted by 전해구 (기계공학과 졸업생, +4). Congratulations!

Here is the best solution of problem 2021-16.