Art of Problem Solving
Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

← Older edit
Metrixgo (talk | contribs)
editor
43 edits
No edit summary
Imosilver (talk | contribs)
13 edits
m →Problem: Use HTML italics for defined term rather than LaTeX
 
(14 intermediate revisions by 10 users not shown)
Line 2: Line 2:


==Problem==
==Problem==
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>?
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>
<imath>\textbf{(A) } 8 \qquad\textbf{(B) } 9 \qquad\textbf{(C) } 10 \qquad\textbf{(D) } 11 \qquad\textbf{(E) } 12</imath>


==Solution 1 (Those who know)==
==Solution 1==
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].
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>.
 
~Tacos_are_yummy_1


~metrixgo
~nithins minor edit


== Solution 2(Quicksolve) ==
== 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 10.
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
~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==
==Solution 3==
Line 32: Line 41:
The numbers in <imath>\{1, ..., m\}</imath> can be grouped as:
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>.
<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>.
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>.
Since <imath>m \le 20</imath>, the maximum size of <imath>A</imath> is <imath>m/2 \le 20/2 = 10</imath>.
Line 41: Line 50:
The numbers in <imath>\{1, ..., m\}</imath> can be grouped as:
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>.
<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>.
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>.
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>.
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.
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)==
==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 distinct members of the set is <imath>11 + 11 = 22</imath> which is greater than any of the elements.
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==
==Chinese Video Solution==
Line 60: Line 79:
~metrixgo
~metrixgo


==Video Solution 1 by OmegaLearn==
==Video Solution by OmegaLearn==
https://youtu.be/GgNQ2yDGIRg
https://youtu.be/GgNQ2yDGIRg


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

See Also

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

These problems are copyrighted © by the Mathematical Association of America.

Retrieved from "https://wiki.aopstest.com/wiki/index.php?title=2025_AMC_12A_Problems/Problem_15&oldid=268679"