Problem:
Let n be a positive integer. Determine the size of the largest subset of
{−n,−n+1,…,n−1,n}
which does not contain three elements a,b,c (not necessarily distinct) satisfying a+b+c= 0 .
Solution:
The maximum size is n if n is even, and n+1 if n is odd, achieved by the subset
{−n,…,−⌊2n​⌋−1,⌊2n​⌋+1,…,n}
Lemma. Let A,B be finite nonempty subsets of Z. Then the set A+B= {a+b:a ∈ A, b ∈B} has cardinality at least ∣A∣+∣B∣−1.
Proof: Write A = {a1​,..., al​} and B = {b1​,...,bm​} with a1​<...<al​ and b1​<...<bm​ Then
a1​+b1​,…,a1​+bm​,a2​+bm​,…,al​+bm​
is a strictly increasing sequence of l+m−1 elements of A+B.
Let S be a subset of {−n,…,n} with the desired property; clearly 0∈/S. Put A= S∩{−n,…,−1} and B=S∩{1,…,n}. Then A+B and −S={−s:s∈S} are disjoint subsets of {−n,…,n}, so by the lemma,
2n+1≥∣A+B∣+∣−S∣≥∣A∣+∣B∣−1+∣S∣=2∣S∣−1
or ∣S∣≤n+1. If n is odd, we are done.
If n is even, we must still show that ∣S∣=n+1 is impossible. Since A+B \subseteq{-n+$ 1,…,n−1}, we cannot achieve the equality 2n+1=∣A+B∣+∣−S∣ unless −n,n∈−S, or equivalently −n,n∈S. Since −n∈S, each of the sets
{1,n−1},...,{n/2−1,n/2+ 1}, {n/2} must contain an element not in B. Thus ∣B∣≤n/2, and similarly ∣A∣≤n/2, contradicting the hypothesis ∣S∣=n+1.
This problem was suggested by Kiran Kedlaya with Tewodros Amdeberhan.
The problems on this page are the property of the MAA's American Mathematics Competitions