Let $n\ge 2,$ be a positive integer. Numbers $\{1,2,3, ...,n\}$ are written in a row in an arbitrary order. Determine the smalles positive integer $k$ with the property: everytime it is possible to delete $k$ numbers from those written on the table, such that the remained numbers are either in an increasing or decreasing order.
Problem
Source: Moldova TST 2019
Tags: combinatorics
10.03.2019 18:51
https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem
10.03.2019 18:53
It is just a direct application of Erdos-Szekeres Theorem. You have at least $\lceil \sqrt{n} \rceil$ numbers in increase order or in decrease order, so the minimum $k$ is at least $n- \lceil \sqrt{n} \rceil$. For an example, let $n=a^2+r$, with $0 < r \le 2a$ (note that $a=\lfloor \sqrt{n} \rfloor = \lceil \sqrt{n} \rceil -1$ and consider the numbers in the order $X_{a+1},X_a,...,X_1$, where: $$ X_{a+1} = a^2+1,..., a^2 +r; X_a=a(a-1)+1,...,a^2; X_(a-1)=a(a-2)+1,...,a(a-1);...;X_1=a(1-1)+1,...,a $$ If $a+2$ numbers remains in the end, satisfying the question, then they are in increasing order, since two of then are on the same $X_i$. However, there also two numbers on different $X_I,X_j$ as well, so they are in decreasing order, a contradiction. The example for $r=0$ is similar, because $X_{a+1}$ is empty and $\lfloor \sqrt{n} \rfloor = \lceil \sqrt{n} \rceil =a$. So, $k=n- \lceil \sqrt{n} \rceil$.
27.04.2019 09:54
Davi Medeiros wrote: However, there also two numbers on different $X_I,X_j$ as well, so they are in decreasing order, a contradiction. In case $r >a+1$ if we remain the set $X_{a+1}$, $r $ numbers will be an increasing order. I think there is a mistake. Who knows correct solution?
28.04.2019 16:00
Who can kill this problem??????
05.06.2019 05:18
Just split the integers $1,2,3..,n$ into $\lceil \sqrt n \rceil$consecutive chunks each of size at most $\lceil\sqrt n\rceil$ ( so that the size of all chunks differ by at most $1$) and order each chunk internally in decreasing order .