# Solution: 2021-12 A graduation ceremony

In a graduation ceremony, $$n$$ graduating students form a circle and their diplomas are distributed uniformly at random. Students who have their own diploma leave, and each of the remaining students passes the diploma she has to the student on her right, and this is one round. Again, each student with her own diploma leave and each of the remaining students passes the diploma to the student on her right and repeat this until everyone leaves. What is the probability that this process takes exactly $$k$$ rounds until everyone leaves.

The best solution was submitted by 고성훈 (수리과학과 2018학번, +4). Congratulations!

GD Star Rating

# Solution: 2021-06 A nondecreasing subsequence

Let $$\mathcal{A}_n$$ be the collection of all sequences $$\mathbf{a}= (a_1,\dots, a_n)$$ with $$a_i \in [i]$$ for all $$i\in [n]=\{1,2,\dots, n\}$$. A nondecreasing $$k$$-subsequence of $$\mathbf{a}$$ is a subsequence $$(a_{i_1}, a_{i_2},\dots, a_{i_k})$$ such that $$i_1< i_2< \dots < i_k$$ and $$a_{i_1}\leq a_{i_2}\leq \dots \leq a_{i_k}$$. For given $$k$$, determine the smallest $$n$$ such that any sequence $$\mathbf{a}\in \mathcal{A}_n$$ has a nondecreasing $$k$$-subsequence.

The best solution was submitted by 고성훈 (수리과학과 2018학번, +4). Congratulations!

Here is his solution of problem 2021-06.

Another solution was submitted by 강한필 (전산학부 2016학번, +3).

GD Star Rating

# Solution: 2021-04 Product of matrices

For an $$n \times n$$ matrix $$M$$ with real eigenvalues, let $$\lambda(M)$$ be the largest eigenvalue of $$M$$. Prove that for any positive integer $$r$$ and positive semidefinite matrices $$A, B$$,

$[\lambda(A^m B^m)]^{1/m} \leq [\lambda(A^{m+1} B^{m+1})]^{1/(m+1)}.$

The best solution was submitted by 고성훈 (수리과학과 2018학번, +4). Congratulations!

Here is his solution of problem 2021-04.

Another solutions was submitted by 김건우 (수리과학과 2017학번, +3),

GD Star Rating

# Solution: 2020-24 Divisions of Fibonacci numbers and their remainders

For each $$i \in \mathbb{N}$$, let $$F_i$$ be the $$i$$-th Fibonacci number where $$F_0=0, F_1=1$$ and $$F_{i+1}=F_{i}+F_{i-1}$$ for each $$i\geq 1$$.
For $$n>m$$, we divide $$F_n$$ by $$F_m$$ to obtain the remainder $$R$$. Prove that either $$R$$ or $$F_m-R$$ is a Fibonacci number.

The best solution was submitted by 고성훈 (수리과학과 2018학번, +4). Congratulations!

Here is his solution of problem 2020-24.

Other solutions was submitted by Abdirakhman Ismail (2020학번), 이준호 (수리과학과 2016학번, +3).

GD Star Rating

# Solution: 2020-02 union of subgroups

Either find an example of a group which is expressed as the union of two proper subgroups or prove that such a group cannot exist.

The best solution was submitted by 고성훈 (수리과학과 2018학번). Congratulations!

Here is his solution of problem 2020-02.

Other solutions were submitted by 구은한 (수리과학과 2019학번, +3), 김기수 (수리과학과 2018학번, +3), 김동률 (수리과학과 2015학번, +3), 박현영 (전기및전자공학부 2016학번, +3), 유찬진 (수리과학과 2015학번, +3), 이준호 (2016학번, +3), 장우영 (서울대 경제학과, +3).

GD Star Rating

# Solution: 2019-21 Approximate isometry

Let $$A$$ be an $$m \times n$$ matrix and $$\delta \in (0, 1)$$. Suppose that $$\| A^T A – I \| \leq \delta$$. Prove that all singular values of $$A$$ are contained in the interval $$(1-\delta, 1+\delta)$$.

The best solution was submitted by 고성훈 (수리과학과 2018학번). Congratulations!

Here is his solution of problem 2019-21.

A similar solution was submitted by 김태균 (수리과학과 2016학번, +3). Incomplete solutions was submitted by 박재원 (2019학번, +2), 하석민 (수리과학과 2017학번, +2).

GD Star Rating

# Concluding 2018 Spring

Thanks all for participating POW actively. Here’s the list of winners:

1st prize (Gold): Lee, Jongwon (이종원, 수리과학과 2014학번)
2nd prize (Silver): Chae, Jiseok (채지석, 수리과학 과 2016학번)
2nd prize (Silver): Han, Joon Ho (한준호,수리과학과 2015학번)
2nd prize (Silver): Lee, Bonwoo (이본우, 수리과학과 2017학번)
3rd prize (Bronze): Ko, Sunghun (고성훈, 2018학번)

이종원 (수리과학과 2014학번) 40/40
채지석 (수리과학과 2016학번) 35/40
한준호 (수리과학과 2015학번) 35/40
이본우 (수리과학과 2017학번) 32/40
고성훈 (2018학번) 20/40
김태균 (수리과학과 2016학번) 19/40
최인혁 (물리학과 2015학번) 10/40
김건우 (수리과학과 2017학번) 8/40
최백규 (생명과학과 2016학번) 6/40
하석민 (수리과학과 2017학번) 6/40
길현준 (2018학번) 3/40
강한필 (전산학부 2016학번) 3/40
문정욱 (2018학번) 3/40
노우진 (물리학과 2015학번) 1/40
윤정인 (물리학과 2016학번) 1/40

GD Star Rating