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

Latest revision as of 20:14, 11 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

Let our subset be $\{11,12,13,...,20\}.$ If we add any element from the set $\{1,2,3,...,10\}$ to our current subset, we will have to remove at least one element from our subset. Hence, the maximum size of our subset is $\boxed{\text{(C) }10}$ .

~Tacos_are_yummy_1

~nithins minor edit

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 $\boxed{\text{(C) }10}$ .

~Kevin Wang

~nithins minor edit

Note (Those who know)

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

~metrixgo

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$ .

$A$ contains $m$ .
$A$ cannot contain $k$ , because $k+k = 2k = m$ , which is in $A$ .
$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$ .

$A$ contains $m$ .
$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 = \boxed{\textbf{(C) } 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$ .

Solution 4 (Another quicksolve)

Note that selecting integers from $\{11, 12, ..., 20\}$ also satisfy the constraints of the problem. The minimum sum of any two members of the set is $11 + 11 = 22$ which is greater than any of the elements.

Solution 5 (with quick proof)

As all of the above solutions point out, the set $\{11, ..., 20\}$ satisfies the required condition, and so the greatest size of a sum-free set is no less than 10. How do we know that 11 isn't possible? Induction is our friend here.

We want to prove that the set $\{1, ..., 2n\}$ has a sum-free set of size no more than $n$ . It is obvious for $n=1$ . Suppose it is true for $n-1$ . Now let $S$ be a sum-free subset of $\{1, ..., 2n\}$ and that it has at least $n+1$ elements. The intersection of $S$ and $\{1, ..., 2n-2\}$ is sum-free, so it has no more than $n-1$ elements. So we must include both $2n-1$ and $2n$ into $S$ . If so, then $1$ and $n$ cannot belong to $S$ .

We are now searching for $n-1$ more elements. But we can make $n-2$ 'pigeonholes': $\{2, 2n-2\}, \{3, 2n-3\}, ..., \{n-1, n+1\}$ , seeing that they can provide no more than $n-2$ elements because each pigeonhole will have a sum of $2n$ .

Video Solution (Really Easy in 2 Mins)

https://youtu.be/V_zh78Ae8xw?si=XAqyWvFhETXUWmCc ~ Pi Academy

Chinese Video Solution

https://www.bilibili.com/video/BV1cLkQBpEhU/

~metrixgo

Video Solution by OmegaLearn

https://youtu.be/GgNQ2yDGIRg

Video Solution by SpreadTheMathLove

https://www.youtube.com/watch?v=dAeyV60Hu5c

@@ Line 1: / Line 1: @@
-==Problem 15==
+{{duplicate|[[2025 AMC 10A Problems/Problem 21|2025 AMC 10A #21]] and [[2025 AMC 12A Problems/Problem 15|2025 AMC 12A #15]]}}
-A set of numbers is called <imath>sum</imath>-<imath>free</imath> if whenever <imath>x</imath> and <imath>y</imath> are (not necessarily distinct) elements of the set, <imath>x+y</imath> is not an element of the set. For example, <imath>\{1,4,6\}</imath> and the empty set are sum-free, but <imath>\{2,4,5\}</imath> is not. What is the greatest possible number of elements in a sum-free subset of <imath>\{1,2,3,...,20\}</imath>?
+==Problem==
+A set of numbers is called <i>sum-free</i> if whenever <imath>x</imath> and <imath>y</imath> are (not necessarily distinct) elements of the set, <imath>x+y</imath> is not an element of the set. For example, <imath>\{1,4,6\}</imath> and the empty set are sum-free, but <imath>\{2,4,5\}</imath> is not. What is the greatest possible number of elements in a sum-free subset of <imath>\{1,2,3,...,20\}</imath>?
 <imath>\textbf{(A) } 8 \qquad\textbf{(B) } 9 \qquad\textbf{(C) } 10 \qquad\textbf{(D) } 11 \qquad\textbf{(E) } 12</imath>
-[[2025 AMC 10A Problems/Problem 21|Solution]]
+==Solution 1==
+Let our subset be <imath>\{11,12,13,...,20\}.</imath> If we add any element from the set <imath>\{1,2,3,...,10\}</imath> to our current subset, we will have to remove at least one element from our subset. Hence, the maximum size of our subset is <imath>\boxed{\text{(C) }10}</imath>.
-== Solution 1(Quicksolve) ==
+~Tacos_are_yummy_1
-Notice that an odd number plus an odd number always results in an even number. Consider the subset of all odd numbers <imath>S = \{1, 3, 5, ..., 19\}</imath>. 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.
+~nithins minor edit
-==Solution 2==
+== 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 <imath>S = \{1, 3, 5, ..., 19\}</imath>. The addition of any even number will result in a violation of the rules, so the maximum number of elements in this subset is <imath>\boxed{\text{(C) }10}</imath>.
+~Kevin Wang
+~nithins minor edit
+==Note (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].
+~metrixgo
+==Solution 3==
 Let <imath>S = \{1, 2, 3, ..., 20\}</imath>. We are looking for the largest possible sum-free subset <imath>A \subseteq S</imath>.
@@ Line 26: / Line 41: @@
 The numbers in <imath>\{1, ..., m\}</imath> can be grouped as:
 <imath>\{ (1, 2k-1), (2, 2k-2), ..., (k-1, k+1) \}</imath> along with the numbers <imath>k</imath> and <imath>m=2k</imath>.
-\item <imath>A</imath> contains <imath>m</imath>.
+* <imath>A</imath> contains <imath>m</imath>.
-\item <imath>A</imath> cannot contain <imath>k</imath>, because <imath>k+k = 2k = m</imath>, which is in <imath>A</imath>.
+* <imath>A</imath> cannot contain <imath>k</imath>, because <imath>k+k = 2k = m</imath>, which is in <imath>A</imath>.
-\item <imath>A</imath> can contain at most one number from each of the <imath>k-1</imath> pairs.
+* <imath>A</imath> can contain at most one number from each of the <imath>k-1</imath> pairs.
 The maximum number of elements <imath>A</imath> can contain from <imath>\{1, ..., m\}</imath> is <imath>1 + 0 + (k-1) = k = m/2</imath>.
 Since <imath>m \le 20</imath>, the maximum size of <imath>A</imath> is <imath>m/2 \le 20/2 = 10</imath>.
@@ Line 35: / Line 50: @@
 The numbers in <imath>\{1, ..., m\}</imath> can be grouped as:
 <imath>\{ (1, 2k-2), (2, 2k-3), ..., (k-1, k) \}</imath> along with <imath>m=2k-1</imath>.
-\item <imath>A</imath> contains <imath>m</imath>.
+* <imath>A</imath> contains <imath>m</imath>.
-\item <imath>A</imath> can contain at most one number from each of the <imath>k-1</imath> pairs.
+* <imath>A</imath> can contain at most one number from each of the <imath>k-1</imath> pairs.
 The maximum number of elements <imath>A</imath> can contain from <imath>\{1, ..., m\}</imath> is <imath>1 + (k-1) = k</imath>.
 Since <imath>m = 2k-1</imath>, we have <imath>k = (m+1)/2</imath>.
 The largest possible odd <imath>m</imath> is 19. If <imath>m=19</imath>, <imath>k = (19+1)/2 = 10</imath>.
-So the maximum size of <imath>A</imath> is <imath>(m+1)/2 \le (19+1)/2 = 10</imath>.
+So the maximum size of <imath>A</imath> is <imath>(m+1)/2 \le (19+1)/2 = \boxed{\textbf{(C) } 10}</imath>.
 In all cases, a sum-free subset of <imath>S</imath> can have at most 10 elements.
-Since we found a set with 10 elements, the greatest possible number of elements is 10.
+Since we found a set with 10 elements, the greatest possible number of elements is <imath>10</imath>.
+==Solution 4 (Another quicksolve)==
+Note that selecting integers from <imath>\{11, 12, ..., 20\}</imath> also satisfy the constraints of the problem. The minimum sum of any two members of the set is <imath>11 + 11 = 22</imath> which is greater than any of the elements.
+==Solution 5 (with quick proof)==
+As all of the above solutions point out, the set <imath>\{11, ..., 20\}</imath> satisfies the required condition, and so the greatest size of a sum-free set is no less than 10. How do we know that 11 isn't possible? Induction is our friend here.
+We want to prove that the set <imath>\{1, ..., 2n\}</imath> has a sum-free set of size no more than <imath>n</imath>. It is obvious for <imath>n=1</imath>. Suppose it is true for <imath>n-1</imath>. Now let <imath>S</imath> be a sum-free subset of <imath>\{1, ..., 2n\}</imath> and that it has at least <imath>n+1</imath> elements. The intersection of <imath>S</imath> and <imath>\{1, ..., 2n-2\}</imath> is sum-free, so it has no more than <imath>n-1</imath> elements. So we must include both <imath>2n-1</imath> and <imath>2n</imath> into <imath>S</imath>. If so, then <imath>1</imath> and <imath>n</imath> cannot belong to <imath>S</imath>.
+We are now searching for <imath>n-1</imath> more elements. But we can make <imath>n-2</imath> 'pigeonholes': <imath>\{2, 2n-2\}, \{3, 2n-3\}, ..., \{n-1, n+1\}</imath>, seeing that they can provide no more than <imath>n-2</imath> elements because each pigeonhole will have a sum of <imath>2n</imath>.
+== Video Solution (Really Easy in 2 Mins) ==
+https://youtu.be/V_zh78Ae8xw?si=XAqyWvFhETXUWmCc ~ Pi Academy
+==Chinese Video Solution==
+https://www.bilibili.com/video/BV1cLkQBpEhU/
+~metrixgo
+==Video Solution by OmegaLearn==
+https://youtu.be/GgNQ2yDGIRg
+==Video Solution by SpreadTheMathLove==
+https://www.youtube.com/watch?v=dAeyV60Hu5c
+==See Also==
+{{AMC10 box|year=2025|ab=A|num-b=20|num-a=22}}
+{{AMC12 box|year=2025|ab=A|num-b=14|num-a=16}}
+{{MAA Notice}}

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