6a Let n 1 be an integer How many distinct integers would y

6.(a)
Let n > 1 be an integer. How many distinct integers would you need to ensure that you have two integers with a sum or difference that is a multiple of n?

Solution

Let us take 2n consecutive integers: a + 1, a + 2, ..., a + 2n - 1, a + 2n,

there are n pairs of numbers that differ by n: (a+1, a+n+1), (a + 2, a + n + 2), ..., (a + n, a + 2n).

Therefore, by Pigeonhole Principle, if one selects more than n numbers from the set, two are liable to belong to the same pair that differ by n.

So we will need atleast n+1 distinct integers from the set to make sure that we have atleast two integers whose sum or difference is n or multiple of n.