# 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

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 .

• HINT:remainder of -a is different from +a,and you have $-a_j$ and $a_j$ – kingW3 Mar 9 '14 at 10:08

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?
• there are 2014 holes. but i don't understand what do you mean by $\pm a_i$ – Boris Morozov Mar 9 '14 at 10:21
• If for e.g. $a_i$ and $-a_j$ have the same remainder, then $a_i + a_j$ is divisible by $2014$. So we can search for matches in remainders of all numbers of form $a_i$ or $-a_i$. – Macavity Mar 9 '14 at 11:04
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