Let $n\in \mathbb{N}$. A sequence $(y_i)$ with $0\le i\le 2^n-1$ is called beautiful of rank $n$ if for all $0\le i\le 2^n-1$, $0\le y_i\le i$. For a beautiful sequence $(y_i)$ of rank $n$ let $A((y_i))$ be the size of the maximal nondecreasing subsequence of $(y_i)$. Find $min \ A(y_i)$ over all beautiful sequences of rank $n$.
It can be shown by a straightforward example that this number cannot exceed $n+1$ as is shown in the attached picture which is easily generalizable by induction. We take $y_{2^n-1}=0, y_{2^n-2}=1, \cdots, y_{2^{n-1}}=2^{n-1}-1$, and redoing this. I think there always should be a non-decreasing subsequence of that size but I couldn't prove it.
I feel $n + 1$ is the correct answer. We can argue this by induction. The case $n = 1$ is trivial.
Suppose we know the result for all smaller $n' < n$, and suppose for the sake of contradiction that there is a counterexample for $n$. The main claim is that for every $0 \leq i \leq n - 1$, every number $a \in [2^i, 2^{i + 1} - 1]$ must appear in the sequence $A$ for at most $n - i - 1$ times. Otherwise, we can form an non-decreasing subsequence of length $n + 1$ by taking a non-decreasing subsequence of length $i + 1$ in $A[0, 2^{i} - 1]$, followed by all occurrence of $a$.
Summing the number of appearance over all such $a$, we conclude that the number of non-zero terms in the sequence $A$ is at most $$\sum_{i = 0}^{n - 1} (n - i - 1) \cdot 2^i = \sum_{j = 0}^{n - 2} \sum_{i = 0}^j 2^i = \sum_{j = 0}^{n - 2} (2^{j + 1} - 1) = 2^n - n - 1.$$ However, this means that $0$ must appear at least $n + 1$ times, so all occurrence of $0$ forms a non-decreasing subsequence, contradiction.