Notice that by solving the equations we get $c = \frac{y+z-x}{2}, b = \frac{x+y-z}{2}, a = \frac{x+z-y}{2}$. We want these to be pairwise distinct. Suppose $c=b$. Then we get $z-x = x-z$, absurd unless $x=z$ which cannot happen. If $c=a$, we have $y-x = x-y$, again impossible. If $a=b$ we have $y-z = z-y$, impossible. Hence $a,b,c$ will always be distinct. Notice $a,b,c \in S$ no matter what given they are integers and $x < y+z$, $y < x+z, z < x+y$ because $1 \le x,y,z \le 2012$ so $1 \le a,b,c \le 2012$ if those two conditions hold. $a,b,c$ are integers iff we have $x+y+z \equiv 0 \pmod{2}$. So we need to find the maximum set such that we cannot pick three elements $x < y < z$ such that $x+y+z$ is even and $x+y > z$. It's not hard to show $A = \{1,,2,3,5,7,...,2011\}$ does not work as it's just all the odd numbers so we can't make $x+y+z$ even, and then $2$ added in cause it won't make the second clause ever true. Thus as $|A| = 1007$ we have $k \ge 1008$. We shall show $k = 1008$. Suppose there are $a$ odd numbers in $A$ where $|A| = 1008$ and $1008 - a$ even elements. Suppose there are at least $100$ even elements $a_1 < a_2 < ..., < a_{100}$. Then as $a_{100} - a_1 \le 2010$, we find there exists some $k$ such that $a_{k+1} - a_k \le 21$ because $(a_2 - a_1) + (a_3 - a_2) + ... + (a_{100} - a_{99}) \le 2010$. As the difference is even, we can say $a_{k+1} - a_k \le 20$. Now notice we can find a $j$ different from $k$ such that $a_{j+1} - a_j \le (2010-20)/98 < 21$, hence we can find another difference which is less than $20$. In fact as long as $\frac{2010 - 20z}{99-z} < 22$, we can show there exist $z$ differences where are $\le 20$. We find this holds for all $z < 84$, hence we can find $83$ differences who differ by $\le 20$. Let the difference with the greatest index have index $k$. Then $a_{k+1} - a_k \le 20$ and $a_k \ge 186$ clearly. Now take the second largest index $j$ and have $a_{j+1} - a_j \le 20$ and $a_j \ge 184$. Choose $a_j < a_k < a_{k+1}$ as our triplet of $x,y,z$ and we're good obviously. Thus we can take there are $< 100$ even numbers. This means there are at least $908$ odd numbers $b_1 < b_2 < ... < b_{908}$. Notice $b_{908} - b_1 \le 2010$, hence we can find some $j$ such that $b_{j+1} - b_j \le (2010)/907 < 3$, so $b_{j+1} - b_j = 2$ as it's even and non-zero. Using a similar approach to above we can find there are $z$ elements which differ by $2$ if $\frac{2010 - 2z}{907 - z} < 4$. This holds for $z < 809$, thus we can find $808$ $j$ such that $b_{j+1} - b_j = 2$> Take the largest such $j$, then $b_{j+1} - b_j = 2$ and $b_j \ge 1615$. Now as $|A| = 1008$, we have $A$ has at least $2$ even elements in it and thus it contains an even number $a$ such that $a \ge 4$. Then clearly the triplet $a, b_j, b_{j+1}$ work and thus we're done as we've covered all cases. Therefore we've shown $k \ge 1008$ and $k \le 1008$, hence $k = 1008$ is the minimum $k$.

i think <dinoboy> do a little more than what we need: for show that $k=1008$ works pay attention to this partition : $A_{i}=\left \{ 4i-3 , 4i-2 , 4i-1 , 4i \right \}$ $(i=1 , 2, ... , 503)$ and use pigeonhole principle to derive the statement easily

mlm95 wrote: i think <dinoboy> do a little more than what we need: for show that $k=1008$ works pay attention to this partition : $A_{i}=\left \{ 4i-3 , 4i-2 , 4i-1 , 4i \right \}$ $(i=1 , 2, ... , 503)$ and use pigeonhole principle to derive the statement easily for $A_{1}={1,2,3,4}$,we choose three elements from it,we cannot guarantee two of $a,b,c$ are not equal

Quote: for$ A_{1}={1,2,3,4}$,we choose three elements from it,we cannot guarantee two of $a,b,c$ are not equal if you pay attention to <dinoboy>'s solution he prove that it suffices to find $x , y , z$ such that $x>y>z$ and $y+z>x$ and $x+y+z $ is even and with that partition the rest of of problem is not so obvious as you say its need check some cases by the way its shorter than <dinoboy>'s solution. for example you can easily check that if three of $A_{i}$'s have at least three elements the statement will be proven and ...

actually,we can first prove that there are at most 15 even numbers in $A$(by using recursion and Fibonacci numbers),then by a little discussion on the even number we can achieve it

littletush wrote: Find the smallest positive integer $k$ such that, for any subset $A$ of $S=\{1,2,\ldots,2012\}$ with $|A|=k$, there exist three elements $x,y,z$ in $A$ such that $x=a+b$, $y=b+c$, $z=c+a$, where $a,b,c$ are in $S$ and are distinct integers. My idea for the solution: We solve the complement of this problem , ie we try to come up with the largest possible $k$ such that for every k-element subset $A$ of $S$ there exist no three integers in $A$ such that they form sides of a triangle. Integers $a,b,c$ such that $a<b<c$ serve as sides of triangle iff $a+b>c$. Hence we need for all {three integer ordered tuples) contained in $A$ the condition that $a+b\le c$> More specifically if $A=\{ a_1,a_2,\cdots , a_k\}$ with $a_i<a_{i+1}$ , then it can be shown that our problem is equivalent to finding largest possible $k$ such that for every k-element subset of $S$ of the form mentioned , $a_i+a_{i+1}\le a_{i+2}$. To maximize $k$ it can be shown that all inequalities must be equalities and thus takes birth the Fibonacci sequence . Finally to find the largest possible $k$ we take first two terms to be $1$ and $2$ so that in any other $k$ element subset u may never be able attain the conditions of the problem. through this we find $k=16$ . k is the largest possible such integer such that every k-element subset of $S$ is devoid of any integer triples which can serve as triangle side lengths. and thus $k=17$ is the smallest integer satisfying the original problem.

Click to reveal hidden text

To show $k=1008$ works, I "did" a partition as follow: $A_0=\{1,2,2011\}, $ $A_1=\{3,4,5\}, A_{k+2}=\{6+2k,7+4k,9+4k\} (0\le k\le 500),$ $A_{503}=\{1008,1010,\ldots,2012\}.$ Now, it is not hard to obtain the claim by using Pegeonhole principle. (We could consider some subcase if neccessary.)

who'd prove it with mathematical induction?

The answer is $1008$. Notice that when $k=1007$, we can pick $$A=\{1,2,3,5,7,...,2011\}$$the condition is equivalent to (i): $2|x+y+z$ (ii): $x,y,z$ form the sides of a triangle Now we show by induction that the answer is $n+2$ when $S=\{1,2,...,2n\}$ for all $n\geq 8$. The case $n=8$ is just a straightforward checking. Now for the inductive step, we notice that if $|\{2n-1,2n\}\cup A|\leq 1$ then we are done. Otherwise, both of them belongs to $A$. Then notice that $$3,5,7,...,2n-3$$can not belong to $A$. Meanwhile, only one of $2n-2,2n-4$ can belong to $A$, so we are done.