A list of positive integers is called good if the maximum element of the list appears exactly once. A sublist is a list formed by one or more consecutive elements of a list. For example, the list $10,34,34,22,30,22$ the sublist $22,30,22$ is good and $10,34,34,22$ is not. A list is very good if all its sublists are good. Find the minimum value of $k$ such that there exists a very good list of length $2019$ with $k$ different values on it.
Problem
Source: Mexico National Olympiad 2019 P4
Tags: combinatorics
13.11.2019 04:13
11.06.2024 13:15
A really cool but easy problem. We solve the general problem for a good list of length $\ell$. We claim that the minimum value is given by the function, \[k(\ell) = \lfloor{log_2(\ell)\rfloor}+1\]As a construction, simply consider the list, \[\nu_2(1)+1,\nu_2(2)+1,\dots , \nu_2(\ell)+1\]which works since $2^n < 2^{n+1}<3\cdot 2^n$ for all natural numbers $n$. In order to prove the bound, we proceed inductively. It is easy to see that any good sequence will have a unique maximum element. Say this maximum element $M$ is at position $m$ of the list of length $\ell$. Then, we have 3 types of sub lists of this list. Sub lists which only consist of elements to the left of $M$, sub lists which consist only of elements to the right of $M$ and sub lists which consist both elements to the right and left of $M$. Any sub list of the last type is clearly good since it includes $M$ and $M$ is the unique maximum of the entire list. This implies that both the sub lists of the first $m-1$ elements and the last $\ell - m$ elements must be very good. So, for each of these sub lists to be good we need $k(m-1)$ and $k(\ell-m)$ distinct elements respectively. Thus, \[k(\ell)\ge \text{max}(k(m-1),k(\ell-m))+1\ge k(\lfloor{\frac{\ell}{2}\rfloor})+1\]It is clear that $k(1)=1$, so inducting upon this recurrence we can easily obtain that, \[k(\ell) \ge \lfloor{log_2(\ell)\rfloor}+1\]which finishes the proof.