Find the smallest n such that given any n distinct integers one can always find 4 different integers a, b, c, d such that a + b = c + d mod 20.
Solution
Answer: n = 9.
For n = 8, we have for example {0, 20, 40, 1, 2, 4, 7, 12} which has no two pairs with the same sum mod 20.
Now suppose n > 8. If there are 7 distinct residues mod 20, then these form 21 pairs, so there must be two pairs with the same sum mod 20. So there can only be 6 or less distinct residues. Hence either there are 4 numbers a = b = c = d mod 20, or there are two pairs of numbers a = c mod 20 and b = d mod 20. In either case, we have a + b = c + d mod 20.
© John Scholes
jscholes@kalva.demon.co.uk
30 Aug 2002