Maths WorkshopMaths problems with full solutions
Exercise 2235Combinatorics › Counting principlesOlympiadAdded 5 Nov 2026

Every set of n integers contains a sum-free subset of more than n/3 elements

#probabilistic method#averaging#sum-free sets#modular arithmetic

Statement

A set of integers is *sum-free* if it contains no a,b,ca,b,c (with a=ba=b allowed) such that a+b=ca+b=c. Prove that every set AA of nn non-zero integers has a sum-free subset with more than n3\frac n3 elements.

Hint

Pick a prime p=3k+2p=3k+2 larger than every ∣a∣|a|, a∈Aa\in A. The residues k+1,…,2k+1k+1,\dots,2k+1 form a sum-free set modulo pp. Choose a random xx and keep the elements aa with ax mod pax\bmod p in that middle third; compute the expected size.

Show solutionHide solution

Solution

Idea. Multiply by a random unit modulo a prime and keep the elements landing in a sum-free "middle third".

A suitable prime. There are infinitely many primes p≡2(mod3)p\equiv2\pmod3. Choose such a prime p=3k+2p=3k+2 with p>∣a∣p>|a| for all a∈Aa\in A; then no aa is divisible by pp.

The middle third. Let S={k+1,k+2,…,2k+1}⊂ZpS=\{k+1,k+2,\dots,2k+1\}\subset\mathbb Z_p, so ∣S∣=k+1|S|=k+1. If u,v∈Su,v\in S, then 2k+2≤u+v≤4k+22k+2\le u+v\le4k+2. Modulo p=3k+2p=3k+2 these sums are the residues 2k+2,…,3k+12k+2,\dots,3k+1 and 0,…,k0,\dots,k. None lies in SS. So SS is sum-free modulo pp.

Averaging. For xx uniform in {1,…,p−1}\{1,\dots,p-1\} and fixed a∈Aa\in A, ax mod pax\bmod p is uniform on the non-zero residues. So
Pr⁡[ax∈S]=k+13k+1>13.\Pr[ax\in S]=\frac{k+1}{3k+1}>\frac13.
By linearity, the expected number of a∈Aa\in A with ax mod p∈Sax\bmod p\in S is more than n3\frac n3. Hence some xx gives B={a∈A:ax mod p∈S}B=\{a\in A:ax\bmod p\in S\} with more than n3\frac n3 elements.

BB is sum-free. If a+b=ca+b=c with a,b,c∈Ba,b,c\in B, then multiplying by xx gives ax+bx≡cx(modp)ax+bx\equiv cx\pmod p with ax mod p, bx mod p, cx mod p∈Sax\bmod p,\ bx\bmod p,\ cx\bmod p\in S, contradicting the sum-freeness of SS. ∎

Lesson. Randomise by a dilation in a finite field to bring a hard structure into a nice fixed set, and use linearity of expectation.