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

2

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
    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)2011-02-17
  • 0
    @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?2011-02-17
  • 0
    But the question isn't about the 52 integers, but about the sums and differences you can make of the 52 integers.2011-02-17
  • 0
    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?2011-02-17
  • 0
    @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).2011-02-17
  • 0
    How would I write this formally? (I have a test tomorrow and it is 2am! ^_^) Clearly, for any box between (0,100) and (50,50) would result in a sum that is divisible by 100 because they all sum to 100. There are 50 instances of this and so there must be 2 integers, at least, that do this?2011-02-17
  • 0
    @MR_: There are 51 boxes and 52 pigeons (if you view the remainders). At least two must fall in the same box. If they are the same number, the difference will be divisible by 100. If not, the sum will be. If all the numbers are are 1 modulo 100, then no two will have a sum divisible by 100. So the claim of sum is incorrect. You also need the difference.2011-02-17
  • 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
    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...2011-02-17
  • 0
    $-a_1$ is positive too, because you're working in integers modulo 100.2011-02-17
  • 0
    Here we take into consideration the negative ones, cannot we? And integers mean more than natural integers for the sake of brevity or convention.2011-02-17
  • 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