3
$\begingroup$

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 .

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

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?

$\endgroup$
  • $\begingroup$ there are 2014 holes. but i don't understand what do you mean by $\pm a_i$ $\endgroup$ – Boris Morozov Mar 9 '14 at 10:21
  • $\begingroup$ 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$. $\endgroup$ – Macavity Mar 9 '14 at 11:04
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.