# Solution: 2022-12 A partition of the power set of a set

Consider the power set $$P([n])$$ consisting of $$2^n$$ subsets of $$[n]=\{1,\dots,n\}$$.
Find the smallest $$k$$ such that the following holds: there exists a partition $$Q_1,\dots, Q_k$$ of $$P([n])$$ so that there do not exist two distinct sets $$A,B\in P([n])$$ and $$i\in [k]$$ with $$A,B,A\cup B, A\cap B \in Q_i$$.

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

Other solutions were submitted by 박기찬 (KAIST 새내기과정학부 22학번, +3), 김기수 (KAIST 수리과학과 18학번, +3), 신준범 (컬럼비아 대학교 20학번, +3), 이종서 (KAIST 전산학부 19학번, +3).

GD Star Rating

# Solution: 2022-11 groups with torsions

Does there exists a finitely generated group which contains torsion elements of order p for all prime numbers p?

The best solution was submitted by 김기수 (KAIST 수리과학과 2018학번, +4). Congratulations!

GD Star Rating

# Solution: 2022-10 Polynomial with root 1

Prove or disprove the following:

For any positive integer $$n$$, there exists a polynomial $$P_n$$ of degree $$n^2$$ such that

(1) all coefficients of $$P_n$$ are integers with absolute value at most $$n^2$$, and

(2) $$1$$ is a root of $$P_n =0$$ with multiplicity at least $$n$$.

The best solution was submitted by 박기찬 (KAIST 새내기과정학부 22학번, +4). Congratulations!

GD Star Rating

# Solution: 2022-09 A chaotic election

Let $$A_1,\dots, A_k$$ be presidential candidates in a country with $$n \geq 1$$ voters with $$k\geq 2$$. Candidates themselves are not voters. Each voter has her/his own preference on those $$k$$ candidates.

Find maximum $$m$$ such that the following scenario is possible where $$A_{k+1}$$ indicates the candidate $$A_1$$: for each $$i\in [k]$$, there are at least $$m$$ voters who prefers $$A_i$$ to $$A_{i+1}$$.

The best solution was submitted by 이명규 (KAIST 전산학부 20학번, +4). Congratulations!

Other solutions were submitted by 조유리 (문현여고 3학년, +3), 박기찬 (KAIST 새내기과정학부 22학번, +3), 김기수 (KAIST 수리과학과 18학번, +3), 여인영 (KAIST 물리학과 20학번, +3).

GD Star Rating

# Solution: 2022-08 two sequences

For positive integers $$n \geq 2$$, let $$a_n = \lceil n/\pi \rceil$$ and let $$b_n = \lceil \csc (\pi/n) \rceil$$. Is $$a_n = b_n$$ for all $$n \neq 3$$?

The best solution was submitted by 김기수 (KAIST 수리과학과 18학번, +4). Congratulations!

Other solutions were submitted by 조유리 (문현여고 3학년, +3), 이명규 (KAIST 전산학부 20학번, +3), 박기찬 (KAIST 새내기과정학부 22학번, +3), 여인영 (KAIST 물리학과 20학번, +3).

GD Star Rating

# Solution: 2022-07 Coulomb potential

Prove the following identity for $$x, y \in \mathbb{R}^3$$:
$\frac{1}{|x-y|} = \frac{1}{\pi^3} \int_{\mathbb{R}^3} \frac{1}{|x-z|^2} \frac{1}{|y-z|^2} dz.$

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

Other solutions were submitted by 이종민 (KAIST 물리학과 21학번, +3), 박기찬 (KAIST 새내기과정학부 22학번, +3), 김기수 (KAIST 수리과학과 18학번, +3), 여인영 (KAIST 물리학과 20학번, +3), 채지석 (KAIST 수리과학과 대학원생, +3), 이상민 (KAIST 수리과학과 대학원생, +3), 나영준 (연세대학교 의학과 18학번, +3).

GD Star Rating

# Solution: 2022-06 A way of putting parentheses

We have an expression $$x_0 \div x_1 \div x_2 \div \dots \div x_n$$. A way of putting $$n-1$$ left parentheses and $$n-1$$ right parenthese is called ‘parenthesization’ if it is valid and completely clarify the order of operations. For example, when $$n=3$$, we have the following five parenthesizations.
$((x_0\div x_1)\div x_2)\div x_3, \enspace (x_0\div (x_1\div x_2))\div x_3, \enspace (x_0\div x_1)\div (x_2\div x_3),$
$x_0\div ((x_1\div x_2)\div x_3), \enspace x_0\div (x_1\div (x_2\div x_3)).$

(a) For an integer $$n$$, how many parenthesizations are there?
(b) For each parenthesization, we can compute the expression to obtain a fraction with some variables in the numerator and some variable in the denominator. For an integer $$n$$, determine which fraction occur most often. How many times does it occur?

The best solution was submitted by 나영준 (연세대학교 의학과 18학번, +4). Congratulations!

Other (incomplete) solutions were submitted by 조유리 (문현여고 3학년, +2), 이명규 (KAIST 전산학부 20학번, +2), 박기찬 (KAIST 새내기과정학부 22학번, +2), Antonio Recuero Buleje (+2).

GD Star Rating

# Solution: 2022-05 squares of perfect squares

Show that there do not exist perfect squares a, b, c such that $$a^2 + b^2 = c^2$$, provided that a, b, c are nonzero integers.

The best solution was submitted by 박준성 (KAIST 수리과학과 19학번, +4). Congratulations!

Other solutions were submitted by 조유리 (문현여고 3학년, +3), 김예곤 (KAIST 수리과학과 19학번, +3), 이명규 (KAIST 전산학부 20학번, +3), 문강연 (KAIST 새내기과정학부 22학번, +3), 박기찬 (KAIST 새내기과정학부 22학번, +3), 이호빈 (KAIST 수리과학과 대학원생, +3), 김기수 (KAIST 수리과학과 18학번, +3), 이재욱 (KAIST 전기및전자공학부 대학원생, +3).

GD Star Rating

# Solution: 2022-04 Cosine matrix

Prove or disprove the following: There exists a real $$2 \times 2$$ matrix $$M$$ such that $\cos M = \begin{pmatrix} 1 & 2022 \\ 0 & 1 \end{pmatrix}.$

The best solution was submitted by 이종민 (KAIST 물리학과 21학번, +4). Congratulations!

Other solutions were submitted by 조유리 (문현여고 3학년, +3), 김예곤 (KAIST 수리과학과 19학번, +3), 이명규 (KAIST 전산학부 20학번, +3), 문강연 (KAIST 새내기과정학부 22학번, +3), 박기찬 (KAIST 새내기과정학부 22학번, +3), 이호빈 (KAIST 수리과학과 대학원생, +3), 김기수 (KAIST 수리과학과 18학번, +3), 여인영 (KAIST 물리학과 20학번, +3), 권민재 (KAIST 수리과학과 19학번, +3), 채지석 (KAIST 수리과학과 대학원생, +3), 하석민 (KAIST 수리과학과 17학번, +3), 박현영 (KAIST 전자및전자공학부 대학원생, +3), 강한필 (KAIST 전산학부 16학번, +3), 이재욱 (KAIST 전기및전자공학부 대학원생, +3), 나영준 (연세대학교 의학과 18학번, +3).

GD Star Rating
For any positive integer $$n \geq 2$$, let $$B_n$$ be the group given by the following presentation$B_n = < \sigma_1, \ldots, \sigma_{n-1} | \sigma_i \sigma_{i+1} \sigma_i = \sigma_{i+1} \sigma_i \sigma_{i+1}, \sigma_i \sigma_j = \sigma_j \sigma_i >$where the first relation is for $$1 \leq i \leq n-2$$ and the second relation is for $$|i-j| \geq 2$$. Show that there exists a total order < on $$B_n$$ such that for any three elements $$a, b, c\in B_n$$, if $$a < b$$ then $$ca < cb$$.