# 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-22 Regular simplex

Let $$S$$ be the unit sphere in $$\mathbb{R}^n$$, centered at the origin, and $$P_1 P_2 \dots P_{n+1}$$ a regular simplex inscribed in $$S$$. Prove that for a point $$P$$ inside $$S$$,
$\sum_{i=1}^{n+1} (PP_i)^4$
depends only on the distance $$OP$$ (and $$n$$).

The best solution was submitted by 이준호 (수리과학과 2016학번, +4). Congratulations!

Here is his solution of problem 2020-22.

Other solutions was submitted by 고성훈 (수리과학과 2018학번, +3), 채지석 (수리과학과 2016학번, +3).

GD Star Rating

# Solution: 2020-19 Continuous functions

Let $$n$$ be a positive integer. Determine all continuous functions $$f: [0, 1] \to \mathbb{R}$$ such that
$f(x_1) + \dots + f(x_n) =1$
for all $$x_1, \dots, x_n \in [0, 1]$$ satisfying $$x_1 + \dots + x_n = 1$$.

The best solution was submitted by 김유일 (2020학번) Congratulations!

Here is his solution of problem 2020-19.

Other solutions was submitted by 길현준 (수리과학과 2018학번, +3), 채지석 (수리과학과 2016학번, +3), 이준호 (수리과학과 2016학번, +2).

GD Star Rating

# Solution: 2020-18 A way of shuffling cards

Consider the cards with labels $$1,\dots, n$$ in some order. If the top card has label $$m$$, we reverse the order of the top $$m$$ cards. The process stops only when the card with label $$1$$ is on the top. Prove that the process must stop in at most $$(1.7)^n$$ steps.

The best solution was submitted by 길현준 (수리과학과 2018학번). Congratulations!

Here is his solution of problem 2020-18.

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

GD Star Rating

# Solution: 2020-17 Endomorphisms of abelian groups

Prove or disprove that a surjective homomorphism from a finitely generated abelian group to itself is an isomorphism.

The best solution was submitted by 김유일 (2020학번). Congratulations!

Here is his solution of problem 2020-17.

A different solution was submitted by 박은아 (수리과학과 2015학번, +3).

GD Star Rating

# Solution: 2020-16 A convex function of matrices

Let $$A$$ be an $$n \times n$$ Hermitian matrix and $$\lambda_1 (A) \geq \lambda_2 (A) \geq \dots \geq \lambda_n (A)$$ the eigenvalues of $$A$$. Prove that for any $$1 \leq k \leq n$$
$A \mapsto \lambda_1 (A) + \lambda_2 (A) + \dots + \lambda_k (A)$
is a convex function.

The best solution was submitted by 채지석 (수리과학과 2016학번). Congratulations!

Here is his solution of problem 2020-16.

Other solutions were submitted by 길현준 (수리과학과 2018학번, +3), 이준호 (수리과학과 2016학번, +3).

GD Star Rating

# Solution: 2020-15 The number of cycles of fixed lengths in random permutations

Let $$m_0=n$$. For each $$i\geq 0$$, choose a number $$x_i$$ in $$\{1,\dots, m_i\}$$ uniformly at random and let $$m_{i+1}= m_i – x_i$$. This gives a random vector $$\mathbf{x}=(x_1,x_2, \dots)$$. For each $$1\leq k\leq n$$, let $$X_k$$ be the number of occurrences of $$k$$ in the vector $$\mathbf{x}$$.

For each $$1\leq k\leq n$$, let $$Y_k$$ be the number of cycles of length $$k$$ in a permutation of $$\{1,\dots, n\}$$ chosen uniformly at random. Prove that $$X_k$$ and $$Y_k$$ have the same distribution.

The best solution was submitted by 이준호 (수리과학과 2016학번). Congratulations!

Here is his solution of problem 2020-15.

GD Star Rating

# Solution: 2020-14 Connecting dots probabilistically

Say there are n points. For each pair of points, we add an edge with probability 1/3. Let $$P_n$$ be the probability of the resulting graph to be connected (meaning any two vertices can be joined by an edge path). What can you say about the limit of $$P_n$$ as n tends to infinity?

The best solution was submitted by 채지석 (수리과학과 2016학번). Congratulations!

Here is his solution of problem 2020-14.

Other solutions were submitted by 강한필 (전산학부 2016학번, +3), 김건우 (수리과학과 2017학번, +3), 이준호 (수리과학과 2016학번, +3), 김유일 (2020학번, +3).

GD Star Rating

# Solution: 2020-12 Draws on a chess tournament

There are $$n$$ people participating to a chess tournament and every two players play exactly one game against each other. The winner receives $$1$$ point and the loser gets $$0$$ point and if the game is a draw, each player receives $$0.5$$ points. Prove that if at least $$3/4$$ of the games are draws, then there are two players with the same total scores.

The best solution was submitted by 채지석 (수리과학과 2016학번). Congratulations!

Here is his solution of problem 2020-12.

Another solution was submitted by 고성훈 (수리과학과 2018학번, +3).

GD Star Rating