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 ?
Suppose our set is then use Try Small Examples: Try Small Examples on .
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)
- AMC 12A 2023 (Problem 22)
- AMC 10A 2025 (Problem 19)
- AMC 10B/12B 2025 (Problem 2/2)
- AMC 10B 2025 (Problem 3)
- AMC 10B/12B 2025 (Problem 17/14)
- AMC 10B 2025 (Problem 18)
- AMC 10B/12B 2025 (Problem 23/19)
- AMC 12B 2025 (Problem 9)
- AMC 12B 2025 (Problem 23)
- AMC 8 2026 (Problem 18)
- AIME I 2026 (Problem 2)
- AIME I 2026 (Problem 15)
- AMC 10A/12A 2020 (Problem 21/19)
- AMC 10B 2022 (Problem 21)