In a sequence $a_1, a_2, . . . , a_{1000}$ consisting of $1000$ distinct numbers a pair $(a_i, a_j )$ with $i < j$ is called ascending if $a_i < a_j$ and descending if $a_i > a_j$ . Determine the largest positive integer $k$ with the property that every sequence of $1000$ distinct numbers has at least $k$ non-overlapping ascending pairs or at least $k$ non-overlapping descending pairs.
Problem
Source: 2022 Dutch IMO TST 1.4
Tags: combinatorics
Dhillonr25
03.12.2022 22:58
you would have to construct a permutation on $P_{1000}$ that gives you half and half
--which is something I'm not completely sure on how to do yet.
mathleticguyyy
18.03.2023 02:52
@above seems to have misread the problem somehow i'm pretty sure that for $n=3k+1$, the answer is $k$. upper bound: $1,2,\ldots,k,3k+1,3k,\ldots,k+1$ lower bound: induct on $k$. the base case $k=0$ is trivial. for the inductive step, note that if the sequence isn't strictly increasing nor decreasing (in these cases we can pair everything), there are indices $x<y<z$ such that $a_y$ is not the median among $a_x,a_y,a_z$. Then, we can first get $k-1$ pairs with the remaining $3(k-1)+1$ numbers and add either $(a_x,a_y)$ or $(a_y,a_z)$.