China Mathematical Olympiad

Without loss of generality, we may assume $a<b<c$. Write $x=a+b$, $z=b+c$, $y=a+c$, then $x<y<z$, $x+y>z$, and $x+y+z$ is even. On the other hand, if there exist $x,y,z\in A$ such that $x<y<z$, $x+y>z$, and $x+y+z$ is even, set $a=\frac{x+y-z}{2}$, $b=\frac{x+z-y}{2}$, $c=\frac{y+z-x}{2}$, it is clear that $a,b,c$ are pairwise distinct elements of $S$, and $x=a+b$, $y=a+c$, $z=b+c$.

The required property is equivalent to the following: for any $k$-element subset $A$ of $S$, there exist three elements $x,y,z\in A$ such that $$x<y<z,x+y>z,\text{ and }x+y+z\text{ is even.}(\ast )$$ If $A=\{1,2,3,5,7,\dots ,2011\}$, $|A|=1007$, and $A$ does not contain three elements satisfying property $(\ast )$. Therefore, $k\ge 1008$.

We next prove that any 1008-element subset of $S$ contains three elements satisfying property $(\ast )$. We prove a general statement: For any integer $n\ge 4$, any $(n+2)$-element subset of $\{1,2,\dots ,2n\}$ contains three elements satisfying $(\ast )$. We induct on $n$.

When $n=4$, let $A$ be a 6-element subset of $\{1,2,\dots ,8\}$, then $A\cap \{3,4,5,6,7,8\}$ contains at least four elements. If $A\cap \{3,4,5,6,7,8\}$ contains three even numbers, then $4,6,8\in A$ satisfying $(\ast )$. If $A\cap \{3,4,5,6,7,8\}$ contains exactly two even numbers, then it contains two odd numbers. For any two odd numbers $x,y$ of $\{3,5,7\}$, two of $(4,x,y)$, $(6,x,y)$, $(8,x,y)$ would satisfy property $(\ast )$, thus one of them is contained in $A$. If $A\cap \{3,4,5,6,7,8\}$ contains exactly one even number $x$, then it contains all three odd numbers, then $(x,5,7)$ satisfies $(\ast )$. The result holds for $n=4$.

Assuming the result holds for $n$ ($n\ge 4$), consider the case of $n+1$. Let $A$ be $(n+3)$-elements of $\{1,2,\dots ,2n+2\}$, if $|A\cap \{1,2,\dots ,2n\}|\ge n+2$. By inductive hypothesis, the result follows. It remains to consider $|A\cap \{1,2,\dots ,2n\}|=n+1$, and $2n+1,2n+2\in A$. If $A$ contains an odd number $x$ in $\{1,2,\dots ,2n\}$, then $x,2n+1,2n+2$ satisfy $(\ast )$; if no odd number of $\{1,2,\dots ,2n\}$ greater than 1 is contained in $A$, then $A=\{1,2,4,6,\dots ,2n,2n+1,2n+2\}$, and $4,6,8\in A$ satisfy $(\ast )$.

Hence, the smallest $k$ with the required property is $1008$.