A set of integers is called sum-free if no element of the set is the sum of any other pair of elements in the set. For example, {1, 10, 100} is sum-free.

Let’s look at pulling out a sum-free subset of a larger set. For example, if we start with {1, 2, 3, …, 10}, then {1, 5, 10} as a sum-free subset. So is {1, 2, 4, 7}. Notice in this case 1 + 2 + 4 = 7, but that’s OK because we’re only concerned with whether an element is the sum of two other elements.

[**Update**: Thanks to Sjoerd Visscher for pointing out that the definition of sum-free does not require that the elements of a sum be distinct. So when I said that the set {1, 2, 4, 7} is sum-free, this was wrong because 2 + 2 = 4. The set *A* is sum-free if the intersection of *A*+*A* with *A* is empty.]

Now let *A* be a set of integers with *n* elements. How large of a sum-free subset does *A* contain? It could be as large as *n* if the set *A* were sum-free to begin with, so that’s an upper bound. But what is a lower bound on the size of the largest sum-free subset?

There is a theorem that gives a number *k* such that every set of *n* non-zero integers contains a sum-free subset of size at least *kn*. You could let *k* be zero, but that’s no fun. Can you find a larger value of *k*? I’ll tell you later what value of *k* the theorem has. Until then, maybe you could try to find your own value.

Suppose you want to write a program to explore this empirically. For a given set, how would you find a maximal sum-free subset? Brute force examination of all subsets would take 2^{n} steps, so hopefully you could do better than that.

What are some sets that have relatively small maximal sum-free subsets?

## Other quiz/puzzle posts