Problem:
A set of numbers is called sum-free if whenever and are (not necessarily distinct) elements of the set, is not an element of the set. For example, and the empty set are sum-free, but is not. What is the greatest possible number of elements in a sum-free subset of
Answer Choices:
A.
B.
C.
D.
E.
Solution:
Note that there are multiple solutions that lead to a set with size - two examples are the odd numbers and .
We aim to prove that elements is impossible. Let the largest element of our subset be , and consider the ordered pairs .
Note that both elements of a pair may not be in , as they would add to . Therefore, we have at most elements, as desired.
Remark. This is a very famous problem in combinatorics, namely the sum-free subset problem. It was proven by ErdΕs that any set of size has a sum-free subset of size at least .
The problems on this page are the property of the MAA's American Mathematics Competitions