40th IMO shortlist 1999/C4 solution

40th IMO 1999 shortlist

Problem C4

Let A be any set of n residues mod n². Show that there is a set B of n residues mod n² such that at least half of the residues mod n² can be written as a + b with a in A and b in B.

Solution

Solution by jys

Let R be the set of all n² residues and let S be the set of all subsets of R with n elements. Let P be the set of all pairs (r, X), where r belongs to R and X belongs to S, such that r cannot be written as a + x for any a in A, x in X.

For any given r, there are (n²-n)Cn subsets X in S such that (r, X) is in P. But (n²-n)Cn ≤ ½ (n²Cn), so at most half the subsets X have (r, X) in P (for any given r). Hence for some B in S, at most half the elements r of R have (r, B) in P. So for this B at least half the elements of R can be written as a + b with a in A and b in B.

(Note that (n²Cn/(n²-n)Cn = (n²(n²-1)(n²-2) ... (n²-n+1)/( (n²-n)(n²-n-1) ... (n²-2n+1) ) ≥ (n²/(n²-n) = (1 + 1/(n-1) )ⁿ > e > 2. )

40th IMO shortlist 1999