IMO 1998 SL 16

Origin: UKR

Problem

Determine the smallest integer n \geq4 for which one can choose four different numbers a, b, c, and d from any n distinct integers such that a + b −c −d is divisible by 20.

Solution

Let S be a set of integers such that for no four distinct elements a, b, c, d \in S, it holds that 20 | a + b −c −d. It is easily seen that there cannot exist distinct elements a, b, c, d with a \equivb and c \equivd (mod 20). Consequently, if the elements of S give k different residues modulo 20, then S itself has at most k + 2 elements. Next, consider these k elements of S with different residues modulo 20. They give k(k−1) different sums of two elements. For k \geq7 there are at least 21 such sums, and two of them, say a+b and c+d, are equal modulo 20; it is easy to see that a, b, c, d are discinct. It follows that k cannot exceed 6, and consequently S has at most 8 elements. An example of a set S with 8 elements is {0, 20, 40, 1, 2, 4, 7, 12}. Hence the answer is n = 9.