# Solution: 2021-24 The squares of wins and losses

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!

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

GD Star Rating

# Solution: 2021-21 Different unions

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!

GD Star Rating

# Solution: 2021-22 Sum of fractions

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!

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

GD Star Rating

# Solution: 2021-21 Different unions

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!

GD Star Rating

# Solution: 2021-20 A circle of perfect squares

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!

GD Star Rating

# Solution: 2021-19 The answer is zero

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!

GD Star Rating

# Solution: 2021-18 Independent sets in a tree

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!

GD Star Rating

# Solution: 2021-16 Optimal constant

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!

GD Star Rating

# Solution: 2021-15 Triangles with integer side lengths

For a natural number $$n$$, let $$a_n$$ be the number of congruence classes of triangles whose all three sides have integer length and its perimeter is $$n$$. Obtain a formula for $$a_n$$.

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

Other solutions were submitted by 강한필 (전산학부 2016학번, +3), 고성훈 (수리과학과 2018학번, +3), 전해구 (기계공학과 졸업생, +3).

GD Star Rating

# Solution: 2021-13 Not convex

Prove or disprove the following:

There exist an infinite sequence of functions $$f_n: [0, 1] \to \mathbb{R} , n=1, 2, \dots$$ ) such that

(1) $$f_n(0) = f_n(1) = 0$$ for any $$n$$,

(2) $$f_n(\frac{a+b}{2}) \leq f_n(a) + f_n(b)$$ for any $$a, b \in [0, 1]$$,

(3) $$f_n – c f_m$$ is not identically zero for any $$c \in \mathbb{R}$$ and $$n \neq m$$.

The best solution was submitted by 김기택 (수리과학과 대학원생, +4). Congratulations!

Other solutions were submitted by 강한필 (전산학부 2016학번, +3), 고성훈 (수리과학과 2018학번, +3), 김민서 (수리과학과 2019학번, +3), 박정우 (수리과학과 2019학번, +3), 신주홍 (수리과학과 2020학번, +3), 이도현 (수리과학과 2018학번, +3), 이본우 (수리과학과 2017학번, +3), 이호빈 (수리과학과 대학원생, +3).

GD Star Rating