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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum