Problem:
Given any nine integers show that it is possible to choose, from among them, four integers such that is divisible by . Further show that such a selection is not possible if we start with eight integers instead of nine.
Solution
Solution:
Suppose there are four numbers among the given nine numbers which leave the same remainder modulo . Then and we are done.
If not, there are two possibilities:
(1) We may have two disjoint pairs and obtained from the given nine numbers such that and . In this case we get .
(2) Or else there are at most three numbers having the same remainder modulo and the remaining six numbers leave distinct remainders which are also different from the first remainder (i.e., the remainder of the three numbers). Thus there are at least distinct remainders modulo that can be obtained from the given set of nine numbers. These remainders give rise to pairs of numbers. By pigeonhole principle, there must be two pairs such that . Going back we get four numbers such that .
If we take the numbers , we check that the result is not true for these eight numbers.