AMC 10A/12A 2025 (Problem 21/15)
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 ?
If , , the answer is since .
If , .
Example or Answer .
Now we want to prove the answer .
Assume on contrary that we can select numbers.
we can select or .
Example or Answer .
Now we want to prove the answer .
Assume on contrary that we can select numbers.
we can select or .
If , .
Example or Answer .
Now we need to prove Answer .
Assume on contrary Answer .
so from each , we have to select at most one element and we need to select and .
we can't select and .
Example or Answer .
Now we need to prove Answer .
Assume on contrary Answer .
so from each , we have to select at most one element and we need to select and .
we can't select and .
or work Answer .
If we want to prove it inductively, prove that we can select at most numbers from to satisfy the property of the main problem.
(I saw this problem in a book 17 years ago.)
(I saw this problem in a book 17 years ago.)
Let's prove Hint 6 by induction.
Base case :
we can select at most one of .
Assume on contrary that from we can select numbers to satisfy the conditions. By induction hypothesis we can select at most elements from to .
Base case :
we can select at most one of .
Assume on contrary that from we can select numbers to satisfy the conditions. By induction hypothesis we can select at most elements from to .
So we have to select and and exactly elements from .
Since we've selected and we need to select elements from to from each subset below, we should select exactly one element.
, from Hint , has already been selected
, and have already been selected
, and have already been selected
Contradiction.
, from Hint , has already been selected
, and have already been selected
, and have already been selected
Contradiction.
(C)