3
$\begingroup$

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!

3 Answers 3

3

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.

6

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.

  • 0
    Ah, yes...I meant 51 (stinky fence post problem!). I think I understand now. Thanks!2011-02-17
5

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

  • 0
    @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.)2011-02-17