Prove:that in any set of 1009 positive integers exits two numbers $a_i$ and $a_j$ such that $a_i-a_j$ or $a_i+a_j$ is divisible by 2014

Question

Show that in any set of 1009 positive integers exits two numbers $a_i$ and $a_j$ such that $a_i-a_j$ or $a_i+a_j$ is divisible by 2014 without remainder ($i\not=j$).

I think the "pigeonholes" here is the remainder of division by 2014 . now i need to think of a way to define the "pigeons" but cant think of anything .

Answer 1

Hint: Pigeons are the remainders when you divide $\pm a_i$ by $2014$. Holes are the possible remainders. How many pigeons and holes are there? And what happens if two pigeons are in the same hole?

Answer 2

We will show that if condition is violated then there cannot be more than 1008 numbers.Lets say x is the residue of some $a_i$ then no other number can have x as residue or -x as residue. Also it will reduce the set by 2 unless and until x=-x which is true for x=1007,0.So the set which violates the above condition can have at most 2012/2+2=1008 elements