2025 AMC 12A Problems/Problem 15: Difference between revisions

Revision as of 02:37, 8 November 2025

The following problem is from both the 2025 AMC 10A #21 and 2025 AMC 12A #15, so both problems redirect to this page.

Problem

A set of numbers is called $sum$ - $free$ if whenever $x$ and $y$ are (not necessarily distinct) elements of the set, $x+y$ is not an element of the set. For example, $\{1,4,6\}$ and the empty set are sum-free, but $\{2,4,5\}$ is not. What is the greatest possible number of elements in a sum-free subset of $\{1,2,3,...,20\}$ ?

$\textbf{(A) } 8 \qquad\textbf{(B) } 9 \qquad\textbf{(C) } 10 \qquad\textbf{(D) } 11 \qquad\textbf{(E) } 12$

Solution 1 (Those who know)

This problem is essentially the same as 2022 AMC 10B Problem 14.

~metrixgo

Solution 2(Quicksolve)

Notice that an odd number plus an odd number always results in an even number. Consider the subset of all odd numbers $S = \{1, 3, 5, ..., 19\}$ . The addition of any even number will result in a violation of the rules, so the maximum number of elements in this subset is 10.

~Kevin Wang

Solution 3

Let $S = \{1, 2, 3, ..., 20\}$ . We are looking for the largest possible sum-free subset $A \subseteq S$ .

First, we show that a sum-free set of size 10 is possible. Consider the set $A_1 = \{11, 12, ..., 20\}$ . The smallest possible sum of two elements (not necessarily distinct) from this set is $11 + 11 = 22$ . Since $22 > 20$ , no sum of two elements from $A_1$ can be in $A_1$ . The size of $A_1$ is $20 - 11 + 1 = 10$ . Thus, a sum-free set of size 10 exists.

Next, we prove that no sum-free set $A \subseteq S$ can have 11 or more elements. Let $m$ be the largest element in $A$ . Since $A$ is sum-free and $m \in A$ , for any $x \in A$ , we must have $m-x \notin A$ (unless $x = m-x$ , in which case $x \notin A$ ). This is because if both $x$ and $m-x$ were in $A$ , their sum $x + (m-x) = m$ would be in $A$ , which is a contradiction.

We can partition the set $\{1, 2, ..., m\}$ into pairs that sum to $m$ , plus any leftover elements.

Case 1: $m$ is even. Let $m = 2k$ . The numbers in $\{1, ..., m\}$ can be grouped as: $\{ (1, 2k-1), (2, 2k-2), ..., (k-1, k+1) \}$ along with the numbers $k$ and $m=2k$ . \item $A$ contains $m$ . \item $A$ cannot contain $k$ , because $k+k = 2k = m$ , which is in $A$ . \item $A$ can contain at most one number from each of the $k-1$ pairs. The maximum number of elements $A$ can contain from $\{1, ..., m\}$ is $1 + 0 + (k-1) = k = m/2$ . Since $m \le 20$ , the maximum size of $A$ is $m/2 \le 20/2 = 10$ .

Case 2: $m$ is odd. Let $m = 2k-1$ . The numbers in $\{1, ..., m\}$ can be grouped as: $\{ (1, 2k-2), (2, 2k-3), ..., (k-1, k) \}$ along with $m=2k-1$ . \item $A$ contains $m$ . \item $A$ can contain at most one number from each of the $k-1$ pairs. The maximum number of elements $A$ can contain from $\{1, ..., m\}$ is $1 + (k-1) = k$ . Since $m = 2k-1$ , we have $k = (m+1)/2$ . The largest possible odd $m$ is 19. If $m=19$ , $k = (19+1)/2 = 10$ . So the maximum size of $A$ is $(m+1)/2 \le (19+1)/2 = 10$ .

In all cases, a sum-free subset of $S$ can have at most 10 elements. Since we found a set with 10 elements, the greatest possible number of elements is 10.

Video Solution 1 by OmegaLearn

https://youtu.be/GgNQ2yDGIRg

@@ Line 7: / Line 7: @@
 ==Solution 1 (Those who know)==
-This problem is essentially the same as [[https://artofproblemsolving.com/wiki/index.php?title=2022_AMC_10B_Problems/Problem_14|2022 AMC 10B Problem 14]]
+This problem is essentially the same as [https://artofproblemsolving.com/wiki/index.php?title=2022_AMC_10B_Problems/Problem_14 2022 AMC 10B Problem 14].
 ~metrixgo

2025 AMC 10A (Problems • Answer Key • Resources)
Preceded by Problem 20	Followed by Problem 22
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 10 Problems and Solutions

2025 AMC 12A (Problems • Answer Key • Resources)
Preceded by Problem 14	Followed by Problem 16
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 Problems and Solutions

Page

Toolbox

Search