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 editNewer edit →
Zhixing (talk | contribs)
editor
101 edits
Stressedpineapple (talk | contribs)
editor
43 edits
No edit summary
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]]}}
 
==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 <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>?


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


[[2025 AMC 10A Problems/Problem 21|Solution]]
==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]]
 
~metrixgo


== Solution 1(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 10.


~Kevin Wang
~Kevin Wang


==Solution 2==
==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>.
Let <imath>S = \{1, 2, 3, ..., 20\}</imath>. We are looking for the largest possible sum-free subset <imath>A \subseteq S</imath>.


Line 50: Line 55:


==See Also==
==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}}
{{AMC12 box|year=2025|ab=A|num-b=14|num-a=16}}
* [[AMC 12]]
* [[AMC 12 Problems and Solutions]]
* [[Mathematics competitions]]
* [[Mathematics competition resources]]
{{MAA Notice}}
{{MAA Notice}}

Revision as of 02:36, 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 [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

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=267498"