Pigeonholes and Remainders

Date: 12/27/2003 at 22:23:31
From: Roshan Upadhyay
Subject: positive integers 

Demonstrate that in any collection of 52 distinct positive integers, 
there are two distinct numbers whose sum or whose difference is 
divisible by 100.

For example, if we take the numbers 

  1, 2, 3, ..., 52 

then one such pair is 

  52 + 48 = 100,  which is divisible by 100

If we take the numbers

  131, 132, 133, ..., 182

then one such pair is 

  132 + 168 = 300, which is divisible by 100 

How can I show that this must be true regardless of which numbers are
chosen? 

Date: 12/28/2003 at 07:41:57
From: Doctor Rob
Subject: positive integers 

Thanks for writing to Ask Dr. Math, Roshan!

Split the 52 numbers into sets S(n) according to their remainder n
when divided by 100, that is, their last two digits.  

If any S(n)contained two or more numbers, then the difference of any
two of them would be divisible by 100.  Thus we assume that no S(n)
contains two numbers.  

Now call the sets S(0), S(1), ..., S(99).  Create the following sets:

   T(n) = S(n) U S(100-n),  n = 1, 2, ..., 49,
   T(0) = S(0),
   T(50) = S(50).

There are 51 of these sets T(n).  The Pigeonhole Principle says
that of the 52 integers, two of them must lie in one of these 51
sets, say T(k).  

Obviously k cannot be 0 or 50.  Since S(k) or S(100-k) have size at
most 1, and their union T(k) has size 2, both must have size exactly
one.  Then the numbers which lie in these two sets must add up to a
multiple of 100.

Feel free to write again if I can help further.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/