The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

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

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 
Associated Topics:
College Number Theory

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.