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 →
Kms888 (talk | contribs)
editor
21 edits
Kms888 (talk | contribs)
editor
21 edits
Line 9: Line 9:
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


==Solution 2==
==Solution 2==

Revision as of 16:42, 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 1(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 2

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