The problem basically says that we need $x,y,z \in A$ satisfying triangle inequality and $x+y+z$ is even $1011$ will work because u can pick all odd numbers and $2$ So now, suppose $|M| \ge 1012$. Then, we must have 2 consecutive pairs of numbers, call them $a < a+1 < b < b+1$ . Then $(a,b,b+1)$ and $(a+1,b,b+1)$ form triangle. One of them will have even sum and so this is the required triple.

It's possible that $a=1$, so your proof doesn't work. Also note that $A=\{ 1,2,3,4,6 \}$ works fine for $M=\{ 1,2,3,4,5,6 \}$, so any solution without bounding is flawed. One possible approach is to prove by induction, begin with $n=4$. You'll need to do messy casework for the base case, but the induction is pretty easy.

Besides being easy, this is just copy paste of China 2012. Would have wished for the problems to be more original in this test!