39th IMO 1998 shortlist Problem N3 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
Solution
: 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. 39th IMO shortlist 1998 © John Scholes [email protected] 30 Aug 2002
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.