IMO Team Selection Test 1

We will prove that the greatest $k$ is $333$. First consider the sequence $1000,999,998,\dots ,669,668,1,2,3,\dots ,666,667$. The first $333$ numbers in the sequence are not usable in an ascending pair, because for each of these numbers the numbers left of it are all greater and the numbers right of it are all smaller. Therefore, for the ascending pairs only the last $667$ numbers are available and that gives at most $333$ non-overlapping ascending pairs. For a descending pair $(a_i,a_j)$ with $i<j$ we get that $a_i$ cannot be one of the numbers $1$ through $667$, because for each of these numbers there are only greater numbers right of it. Hence, $a_i$ must be one of the first $333$ numbers, from which we deduce that there can be at most $333$ non-overlapping descending pairs. We conclude that no $k>333$ will satisfy the conditions.

Now we will prove that for all $t\ge 1$, there are at least $t$ non-overlapping ascending or $t$ non-overlapping descending pairs in any sequence of $3t-1$ distinct numbers. We will prove this by induction on $t$. For $t=1$, the sequence has length $2$ and this pair of numbers is either descending or ascending, which means the statement is correct. Now let $r\ge 1$ and suppose the statement is true for $t=r$. We consider the case $t=r+1$ and take any sequence $a_1,a_2,\dots ,a_{3r+2}$ of $3r+2$ distinct numbers. If the sequence is completely ascending, we can make neighbouring pairs which are all ascending. These are $\lfloor \frac{3r+2}{2}\rfloor \ge \frac{2r+2}{2}=r+1$ pairs. Analogously, if the sequence is fully descending, there are at least $r+1$ descending pairs. If the sequence is not fully ascending and also not fully descending, there is a spot in the sequence where the sequence is first ascending and then descending or the other way around. In other words: there are numbers $a_i,a_{i+1},a_{i+2}$ in the sequence with $a_i<a_{i+1}>a_{i+2}$ or $a_i>a_{i+1}<a_{i+2}$. In both cases, these three numbers contain both an ascending and descending pair. Now apply the induction hypothesis to the sequence $a_1,a_2,\dots ,a_{i-1},a_{i+3},a_{i+4},\dots ,a_{3r+2}$. This is a sequence with $3r+2-3=3r-1$ distinct numbers, so there are at least $r$ non-overlapping ascending pairs or $r$ non-overlapping descending pairs. In the former case, we can add the ascending pair from $a_i,a_{i+1},a_{i+2}$ to it, and in the latter case, we can add the descending pair to it. In this way, we obtain $r+1$ non-overlapping ascending pairs or $r+1$ non-overlapping descending pairs. This completes the induction.

Now substitute $t=333$ in this result: in a sequence consisting of $998$ distinct numbers, there are always at least $333$ non-overlapping ascending pairs or at least $333$ non-overlapping descending pairs. This is also true for a sequence consisting of $1000$ numbers (just ignore the last two numbers).

Hence, $k=333$ satisfies the conditions and is the greatest such $k$. $\square$