Proof by Pigeon hole principle?

Question

I'd like to show that among any $52$ integers, there are two whose sum or difference is divisible by $100$.

Assume all the integers are placed into boxes based on their remainders, then there must be one box $y$ that contains two integers.

If $(a - b) = (100x + y) - (100z + y)$, where $x,z$ are integers.

$= 100(x - z)$, which means $100*\text{integer} = (a - b)$.

Is this valid? I did some other examples, but the number of given integers was odd, which meant that there must be two integers in one box... so when given $52$ that changes things up and I am wondering how that affects the problem and how I solve it?
Any further explanation would be helpful.

Answer 1

Here are soms hints that should lead you to the answer:

• Consider the set $S$ with these numbers: $a_1,a_2,...,a_{51},a_{52},-a_{1},-a_{2},...,-a_{51},-a_{52}$.

• There are 104 numbers to two of them have the same remainder, note that the problem is solved unless these numbers are $a_i$ and $-a_i$

• But if $a_i \equiv -a_i$ then 50 divides $a_i$. If there are two $a_i$ that are divisible by $50$ then their sum (and difference) is divisible by 100. Therefore we may assume there is only one such number.

• So one can leave $a_i$ and $-a_i$ out of the set of 104 numbers, there are 102 numbers remaining. The same argument as before holds, but this time it cannot occur that the numbers found are $a_i$ and $-a_i$.

Answer 2

It is not valid.

You have 100 boxes and 52 integers. Pigeon hole does not apply with the integers being the pigeons...

For a proof which keeps the number of pigeons the same:

Consider the "boxes"

$(0,100), \ (1,99), \ (2, 98), \dots, (50,50)$

There are $52$ pigeons (the remainders of the integers modulo 100) and $51$ boxes.

At least one box must have two integers. If both are $y$, then their difference is divisible by 100. If one is $y$ and the other $100-y$, then their sum is divisible.