Can we try something like this: suppose we want to partition $X$ into $A$ and $B$, Put 1 into $A$, 2 into $B$ put 3,4 into $A$, 5,6 into $B$ put 7,8,9 into $A$, 10, 11, 12 into $B$ ...and so on We can show that this partition satisfies the requirement of the problem via induction. It's easily verifiable for $n=3$. Now for $n$, we see the last two "rows" in the division above: ... we put $(n-2)(n-3) + 1,..., (n-2)^2$ into $A$ and $(n-2)^2+1,...,(n-1)(n-2)$ into $B$ we put $(n-1)(n-2) + 1,..., (n-1)^2$ into $A$ and $(n-1)^2+1,...,n(n-1)$ into $B$ Suppose that there is a subsequence of length $n$ that violates the condition, we consider whether they're in group $A$ or $B$. Case 1: they're in group $A$. We know from the induction hypothesis that there is no subsequence of length $n-1$ in the first $n-2$ rows, because that's exactly the partition we use in the induction hypothesis. So that means that $a_{n-1}$ and $a_n$ are both in the last row. $a_n - a_{n-1} \leq (n-1)^2-(n-1)(n-2)-1 = n-2$ but $a_{n-1} - a_{n-2} \geq (n-1)(n-2) +1 - (n-2)^2 = n-1$ So $a_n - a_{n-1} < a_{n-1}-a_{n-2}$. Contradiction. Case 2: they're in group $B$. As before, we know from the induction hypothesis that $a_{n-1}$ and $a_n$ must both be in the last row. $a_n - a_{n-1} \leq n(n-1)-(n-1)^2-1 = n-2$ but $a_{n-1} - a_{n-2} \geq (n-1)^2 +1 - (n-1)(n-2) = n-1$ again, we derive a contradiction.

It is similar with the official solution. Outline of my proof: The case $n=3$ is trivial, assume $n\ge4$. We call such $n$ elements set a "convex set". Given an increasing sequence of positive integers $d_1,\ldots,d_{n-1}$ with $d_1+\ldots+d_{n-1}=k$, there exist $n^2-n-k$ convex set with $a_{k+1}-a_k=d_k$. Since $d_1+\ldots+d_{n-1}=k$ has at most ${k-1\choose n-2}$ solutions and $n-1\le k\le n^2-n-1$, then the total number of convex set is at most $\sum_{k=n-1}^{n^2-n-1}(n^2-n-k){k-1\choose n-2}<(n^2-2n+1){n^2-n\choose n-1}$. It is easy to verify that this expression is not greater than $2^{n^2-n-1}$ for $n\ge4$. But there are $2^{n^2-n-1}$ possible partition of $X$, so there exist a partition which does not contain any convex set. Is it correct?

Hello, two questions regarding your solution. 1. The inequality that the sum on the LHS is less than the RHS. I'm sure it's true, but I don't yet see an easy way to prove it. But it may not matter that much because eventually you're trying to establish that it's less than $2^{n^-n-1}$. 2. What you proved was that one partition doesn't contain a convex set. But does that guarantee that the other partition also doesn't contain a convex set?

Here is my full proof: For $n=3$ we can take $\{1,3,4\}$ and $\{2,5,6\}$. Suppose that $n\ge4$. Call $\{a_1,a_2,\ldots,a_n\}\subset\{1,2,\ldots,n^2-n\}$ "convex" if $a_1<a_2<\ldots<a_n$ and $a_k\le\frac{a_{k-1}+a_{k+1}}2$ for $k=2,3,\ldots,n-1$. Let $d_1\le d_2\le\ldots\le d_{n-1}$ be positive integers such that $d_1+d_2+\ldots+d_{n-1}=k$. We will count the number of convex sets $\{a_1,a_2,\ldots,a_n\}$ such that $a_{k+1}-a_k=d_k$ for $k=1,\ldots,n-1$. Such convex set can be determined uniquely from $a_n$ and $d_1,d_2,\ldots,d_{n-1}$. Note that $n^2-n\ge a_n\ge1+k$, so there are $n^2-n-k$ possible values for $a_n$ (whence we conclude $k\le n^2-n-1$), and hence, given $d_1,\ldots,d_{n-1}$, we have $n^2-n-k$ convex sets. But $d_1+d_2+\ldots+d_{n-1}=k$ has at most ${k-1\choose n-2}$ solutions in positive integers, so the total number of convex sets is at most \[\sum_{k=n-1}^{n^2-n-1}{k-1\choose n-2}(n^2-n-k).\] We claim that this expression is less than $2^{n^2-n-1}$. We have $n^2-n-k\le n^2-2n+1$ and $\sum_{k=n-1}^{n^2-n-1}{k-1\choose n-2}={n^2-n-1\choose n-1}$, so it suffices to prove that $(n-1)^2{n^2-n-1\choose n-1}<2^{n^2-n-1}$. This is true for $n=4$, now assume $n\ge5$. Note that $n^2>3n+1$, $2n^2-4n-2>n^2-n-1$, $n^2-n-1<(n^2-2n-1)2\le(n^2-2n-1)(n-2)$, $\frac{(n^2-n-1)!}{(n-1)!(n^2-2n)!}<\frac{(n^2-n-2)!}{(n^2-2n-2)!n!}$, ${n^2-n-1\choose n-1}<{n^2-n-2\choose n}$, now it suffices to prove that $(n-1)^2{n^2-n-2\choose n}<2^{n^2-n-1}$. Note that ${n^2-n-2\choose n}={n^2-n-2\choose n}$, ${n^2-n-2\choose n}<{n^2-n-2\choose n+1}$, $\ldots$, ${n^2-n-2\choose n}<{n^2-n-2\choose n^2-2n-3}$, ${n^2-n-2\choose n}={n^2-n-2\choose n^2-2n-2}$. Add all the inequalities and equations, we get $(n^2-3n-1){n^2-n-1\choose n-1}<\sum_{k=n-1}^{n^2-2n}{n^2-n-1\choose k}<2^{n^2-n-2}$. Now it suffices to prove that $2^{n^2-n-2}\frac{n^2-2n+1}{n^2-3n-1}<2^{n^2-n-1}$, which is equivalent to $n^2-2n+1<2n^2-6n-2$, $n^2>4n+3$, which is true for $n\ge5$. Therefore the number of convex set is less than $2^{n^2-n-1}$. There are $2^{n^2-n}$ subsets of $X$. We pair each subset with its complement, there are $2^{n^2-n-1}$ pairs. Since the number of convex sets is less than $2^{n^2-n-1}$, there exist a pair which does not contain pair. QED Note: A pair of subsets contains a convex sets iff at least one of its subset contain a convex set.

How about the converse, I mean, is there a nice bound f(n) that for every positive integer $n \geq 3$, $ X=\{1,2,3,\ldots,f(n)\} $, for each way that we divide X into two non-intersecting subsets, we can find n positive integer $a_{1}<a_{2}<......a_{n} $ in the same subset for which $ a_{k}\le\frac{a_{k-1}+a_{k+1}}{2} $ is right for all $ k=2,\ldots,n-1 $. I can prove $f(n)=n(n^{2}+5)/6$ is able, but I think it's too big.

litongyang wrote: How about the converse, I mean, is there a nice bound f(n) that for every positive integer $n \geq 3$, $ X=\{1,2,3,\ldots,f(n)\} $, for each way that we divide X into two non-intersecting subsets, we can find n positive integer $a_{1}<a_{2}<......a_{n} $ in the same subset for which $ a_{k}\le\frac{a_{k-1}+a_{k+1}}{2} $ is right for all $ k=2,\ldots,n-1 $. I can prove $f(n)=n(n^{2}+5)/6$ is able, but I think it's too big. Anyone notice my problem?