Proof by Pigeon hole principle? 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.
 A: 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.
A: 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$.
A: This question boils down to proving that for $52$ numbers from the set $A=\{0,1,2,\ldots,98,99\}$, there exist two whose sum or difference is divisible by $100$.
There are two cases to consider
$(1)$ Say a number $b \in A$ occurs more than once.
Then, clearly the difference is divisible by $100$.
$(2)$ Suppose no number from $A$ occurs more than once.
Then we can partition $A$ as $\{0\},\{50\},\{1,99\},\{2,98\},\ldots,\{48,52\},\{49,51\}$ into $51$ sets.
We can select the $51$ numbers from each of these partitions.
By, pigeonhole principle the $52^{nd}$ number is forced to share the same partition set with another of the earlier selected $51$ numbers. Thus, the sum of these two numbers is divisible by $100$.
Thus, the claim holds in both of the two cases.
