# 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