# 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-05 Finite generation of a group

Prove or disprove that if all elements of an infinite group G has order less than n for some positive integer n, then G is finitely generated.

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

Here is his solution of problem 2021-05.

Other solutions were submitted by 강한필 (전산학부 2016학번, +3), 고성훈 (수리과학과 2018학번, +3), Late solutions are not graded.

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: 2021-02 Inscribed triangles

Show that for any triangle T and any Jordan curve C in the Euclidean plane, there exists a triangle inscribed in C which is similar to T.

The best solution was submitted by 강한필 (전산학부 2016학번, +4). Congratulations!

Here is his solution of problem 2021-02.

Other solutions was submitted by 하석민 (수리과학과 2017학번, +3), 박은아 (수리과학과 2015학번, +2).

GD Star Rating

# Solution: 2021-01 Single-digit number

Prove that for any given positive integer $$n$$, there exists a sequence of the following operations that transforms $$n$$ to a single-digit number (in decimal representation).

1) multiply a given positive integer by any positive integer.

2) remove all zeros in the decimal representation of a given positive integer.

The best solution was submitted by 강한필 (전산학부 2016학번, +4). Congratulations!

Here is his solution of problem 2021-01.

Other solutions was submitted by 김기수 (수리과학과 2018학번), 박은아 (수리과학과 2015학번, +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-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