Associated Topics || Dr. Math Home || Search Dr. Math

### Pigeonholes and Remainders

Date: 12/27/2003 at 22:23:31
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/
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search