Question

Prove the following:
Show that for any given 107 integers there exist two of them whose sum, or else whose difference, is divisible by 210.

Answer 1

101 Let 9., 92,--., 9107 9,07 be integers. Now, if if atleast two of these numbers are equal. equalele Og = 9j. ju; 1). 107 then. 0; -9j = 0 2014-09 and

are Now suppose all a; 16; 2 107 distinct. As we know for any b. brad, da such that and n b. d(modn) b2 = d2 (modn. and then bi + b2 = 0, +d2 (modn) Here if d + d₂ = n. then b, uby zo(modn)

Now for given numbers a are 9107, If we divide the remainder from 209. by. 2104 o te get It two numbers have remaindos with respect to 210 that add upto. 210. Or O then the sum of those two numbers kwill be divisible 210 ( Above calculation in terme of congruence modulo). by Now, have 106 pairs of possible remainder which add upto. 210: (0,0), (1, 209), (2, 208)..., Clos, 105).

Now, for any two set of integers 2.1, 9212 9107 we have 101 integers and 106 pairs of remainders, only

Consider the Piegenhole principle: simple form

If n + 1 objects are put into n boxes, then at least one box contains two or more objects.

$\vspace$

Thus, for a pair of integers not to have one pair which add up to 210, each integer in the set would have to be a member of a separate pair.

$\vspace$

Since here we have total 107 integers and only 106 pairs of remainder, therefore using the Piegenhole principle;

At least one integer must be in the same pair as another.

$\vspace$

Therefore the sum of the pair is divisible by 210.