# Proving by PigeonHole Principle?

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*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. Thanks!

• 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$.

• I think it may be implied in my book that all integers are positive? In an example, the question does not explicitly state that and the answer only accounts for positive integers... – Mr_CryptoPrime Feb 17 '11 at 8:43
• $-a_1$ is positive too, because you're working in integers modulo 100. – Peter Taylor Feb 17 '11 at 9:45
• Here we take into consideration the negative ones, cannot we? And integers mean more than natural integers for the sake of brevity or convention. – awllower Feb 17 '11 at 12:45
• @Mr_Cryptoprime: If the statement is true for integers $\mathbb Z = \{...,-2,-1,0,1,2,...\}$ then it is of course true for every subset, in particular for $\mathbb N = \{0,1,...\}$ or $\{1,2,...\}$, whatever definition you like most. So it doesn't make a big difference. In fact $\mathbb Z$ is often easiest to consider in these problems, because it is closed under differences (i.e. $\mathbb Z$ is a group whereas $\mathbb N$ is not.) – Myself Feb 17 '11 at 12:54

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.

• How do I solve it then? (problem is out of a book and so it should be solvable and it does state explicitly to use pigeon hole) – Mr_CryptoPrime Feb 17 '11 at 8:40
• @Mr_: Pigeon hole seems so simple, but it can be applied in very subtle ways. Not every problem has such a straightforward application of pigeon hole as you seek. If you take the 52 numbers as is, even if you applied pigeon hole succesfully, you will only show that the difference of two is divisible by 100. Can you find a way to increase the number of pigeons (i.e from 52, go to at least 101) and incorporate the possibility that the sum could also be divisible by 100, if two integers are in the same box? – Aryabhata Feb 17 '11 at 8:45
• But the question isn't about the 52 integers, but about the sums and differences you can make of the 52 integers. – Eivind Feb 17 '11 at 8:46
• The question only demands we prove for difference or sum, shown by presence of 'OR'. However, assuming that it does not specifically exclude negative integers I suppose we could increase the 'pigeons' by including negatives, as @Myself suggested? – Mr_CryptoPrime Feb 17 '11 at 8:49
• @MR_: In fact he has given you the whole proof. Let me see if I can give you a hint to do it in a different way (I will edit the answer). – Aryabhata Feb 17 '11 at 8:50

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.