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

Newer edit →
Jonathanmo (talk | contribs)
editor
24 edits
Created page with "==Problem 21== 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..."
 
Kms888 (talk | contribs)
editor
21 edits
Line 1: Line 1:
==Problem 21==
==Problem 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>?
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>?


Line 5: Line 5:


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

Revision as of 16:40, 6 November 2025

Problem 15

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

Solution

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.

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