China Mathematical Olympiad

Define $$S_k=\{k^2-k+1,k^2-k+2,\dots ,k^2\},$$ $$T_k=\{k^2+1,k^2+2,\dots ,k^2+k\}.$$ Let $S={\bigcup }_{k=1}^{n-1}{S}_k$, $T={\bigcup }_{k=1}^{n-1}{T}_k$. We will prove that $S$, $T$ are the required subsets of $X$. Firstly it is easy to verify that $S\cap T=\varnothing$ and $S\cup T=X$. Next we suppose for contradiction that $S$ contains elements $a_1,a_2,\dots ,a_n$ with $a_1<a_2<\cdots <a_n$ and $a_k\le \frac{a_{k-1}+a_{k+1}}{2}$ for $k=2,\dots ,n-1$. Then we have $$a_k-a_{k-1}\le a_{k+1}-a_k,k=2,\dots ,n-1.\stackrel{◯}{1}$$ Assume that $a_1\in S_i$, we have $i<n-1$, since $|S_{n-1}|<n$. There exists at least $n-|S_i|=n-i$ elements in $\{a_1,a_2,\dots ,a_n\}\cap (S_{i+1}\cup \cdots \cup S_{n-1})$. Applying the pigeonhole principle, we get that there is an $S_j$ ($i<j<n$) which contains at least two elements in $a_1,a_2,\dots ,a_n$. That means there exists $a_k$ such that $a_k,a_{k+1}\in S_j$ and $a_{k-1}\in S_1\cup \cdots \cup S_{j-1}$. Then we have $$a_{k+1}-a_k\le |S_j|-1=j-1,a_k-a_{k-1}\ge |T_{j-1}|+1=j.$$ That means $a_{k+1}-a_k<a_k-a_{k-1}$, contradicting ①.

In the same way, we can prove that $T$ does not contain $a_1,a_2,\dots ,a_n$ with the required properties either. This completes the proof.