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.}\quad (*)$$
If $A = \{1, 2, 3, 5, 7, \dots, 2011\}$, $|A| = 1007$, and $A$ does not contain three elements satisfying property $(*)$. Therefore, $k \ge 1008$.

We next prove that any 1008-element subset of $S$ contains three elements satisfying property $(*)$.
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 $(*)$. 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 $(*)$. 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 $(*)$, 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 $(*)$. 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 $(*)$; 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 $(*)$.

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