Let n 1 be an integer How many distinct integers would you

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

Given a run of 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 the 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.