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

2022 AMC 10B Problems/Problem 14: Difference between revisions

← Older edit
Mathisfun21 (talk | contribs)
editor
6 edits
Pinotation (talk | contribs)
editor
346 edits
 
(40 intermediate revisions by 19 users not shown)
Line 1: Line 1:
==Problem==
==Problem==


Suppose that <math>S</math> is a subset of <math>\left\{ 1, 2, 3, \cdots , 25 \right\}</math> such that the sum of any two (not necessarily distinct)
Suppose that <imath>S</imath> is a subset of <imath>\left\{ 1, 2, 3, \ldots , 25 \right\}</imath> such that the sum of any two (not necessarily distinct) elements of <imath>S</imath> is never an element of <imath>S.</imath> What is the maximum number of elements <imath>S</imath> may contain?
elements of <math>S</math> is never an element of <math>S</math>. What is the maximum number of elements <math>S</math> may contain?


==Solution (Pigeonhole Principle)==
<imath>\textbf{(A)}\ 12 \qquad\textbf{(B)}\ 13 \qquad\textbf{(C)}\ 14 \qquad\textbf{(D)}\ 15 \qquad\textbf{(E)}\ 16</imath>


Denote by <math>M</math> the largest number in <math>S</math>.
==Solution 1 (Pigeonhole Principle)==
We categorize numbers <math>\left\{ 1, 2, \cdots , M-1 \right\}</math> (except <math>\frac{M}{2}</math> if <math>M</math> is even) into <math>\lfloor \frac{M-1}{2} \rfloor</math> groups, such that the <math>i</math>th group contains two numbers <math>i</math> and <math>M-i</math>.
Let <imath>M</imath> be the largest number in <imath>S</imath>.
We categorize numbers <imath>\left\{ 1, 2, \ldots , M-1 \right\}</imath> (except <imath>\frac{M}{2}</imath> if <imath>M</imath> is even) into <imath>\left\lfloor \frac{M-1}{2} \right\rfloor</imath> groups, such that the <imath>i</imath>th group contains two numbers <imath>i</imath> and <imath>M-i</imath>.


Recall that <math>M \in S</math> and the sum of two numbers in <math>S</math> cannot be equal to <math>M</math>, and the sum of numbers in each group above is equal to <math>S</math>. Thus, each of the above <math>\lfloor \frac{M-1}{2} \rfloor</math> groups can have at most one number in <math>S</math>.
Recall that <imath>M \in S</imath> and the sum of two numbers in <imath>S</imath> cannot be equal to <imath>M</imath>, and the sum of numbers in each group above is equal to <imath>S</imath>. Thus, each of the above <imath>\left\lfloor \frac{M-1}{2} \right\rfloor</imath> groups can have at most one number in <imath>S</imath>.
Therefore,
Therefore,
<cmath>
<cmath>
Line 15: Line 15:
|S| & \leq 1 + \left\lfloor \frac{M-1}{2} \right\rfloor \\
|S| & \leq 1 + \left\lfloor \frac{M-1}{2} \right\rfloor \\
& \leq 1 + \left\lfloor \frac{25}{2} \right\rfloor \\
& \leq 1 + \left\lfloor \frac{25}{2} \right\rfloor \\
& = 13 .
& = 13.
\end{align*}
\end{align*}
</cmath>
</cmath>


Next, we construct an instance of <math>S</math> with <math>|S| = 13</math>.
Next, we construct an instance of <imath>S</imath> with <imath>|S| = 13</imath>.
Let <math>S = \left\{ 13, 14, \cdots , 25 \right\}</math>.
Let <imath>S = \left\{ 13, 14, \ldots , 25 \right\}</imath>.
Thus, this set is feasible.
Thus, this set is feasible.
Therefore, the most number of elements in <math>S</math> is
Therefore, the most number of elements in <imath>S</imath> is
<math>\boxed{\textbf{(B) 13}}</math>.
<imath>\boxed{\textbf{(B) }13}</imath>.


~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
== Solution 2 (Pigeonhole v2) ==
We construct a possible subset <imath>S</imath> with <imath>13</imath> elements by including all odd integers from <imath>1</imath> to <imath>25</imath>, inclusive. <imath>S=\left\{ 1, 3, 5, \cdots , 25 \right\}</imath>. The sum of any <imath>2</imath> elements is even, and thus cannot be an element of <imath>S</imath>.
To show that <imath>S</imath> cannot have more than <imath>13</imath> elements, assume for sake of contradiction that <imath>|S| \geq 14</imath>. Let <imath>S=\left\{ x_1, x_2, \cdots , x_n \right\}</imath> where <imath>n \geq 14</imath> and <imath>x_1 < x_2 < \cdots < x_n</imath>. Because the sums of any <imath>2</imath> (not necessarily distinct) elements do not appear in <imath>S</imath>, <imath>x_1+x_i</imath> is not an element of <imath>S</imath> for all <imath>1 \leq i \leq n</imath>. So, <imath>x_1, x_2, \cdots , x_n , x_1+x_1, x_1+x_2, \cdots , x_1+x_n</imath> are all distinct integers. Let these integers be elements of the set <imath>T</imath>. <imath>|T|=2n</imath>, and because <imath>n \geq 14</imath>, <imath>|T| \geq 28</imath>. But all elements of <imath>T</imath> must be <imath>\geq x_1</imath> and <imath>\leq x_1+x_n \leq x_1+25</imath>, leaving only 26 possible values for the elements in <imath>T</imath>. By the Pigeonhole Principle, the elements cannot be distinct, and we have a contradiction.
Thus, <imath> \boxed{\textbf{(B) }13}</imath> is the maximum possible size of <imath>S</imath>.
~starwars101
==Solution 3 (Intuitive and Fast)==
Notice how \( 24 + 25 > 25 \), \( 23 + 24 > 25 \), and this continues backward until \( n + n+1 > 25 \). We then see that \( 2n+1 > 25 \rightarrow 2n > 24 \rightarrow n > 12 \).
Thus the elements in the set must have the property \( n > 12 : n \in \mathbb{Z}^+ \) and therefore our set is \( \{13, 14, 15, \dots, 25\} \) in which there is \( 25 - 13 + 1 \Rightarrow \) <imath> \boxed{\textbf{(B) }13}</imath> elements.
~Pinotation


==Video Solution==
==Video Solution==
Line 32: Line 50:


~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
==Video Solution by Interstigation==
https://youtu.be/in3N3Os5kGw
==Video Solution by TheBeautyofMath==
https://youtu.be/Mi2AxPhnRno?t=1056
~IceMatrix
== See Also ==
[https://artofproblemsolving.com/wiki/index.php?title=2025_AMC_12A_Problems/Problem_15 2025 AMC 10A Q21/AMC 12A Q15]
{{AMC10 box|year=2022|ab=B|num-b=13|num-a=15}}
{{MAA Notice}}

Latest revision as of 15:56, 9 November 2025

Problem

Suppose that $S$ is a subset of $\left\{ 1, 2, 3, \ldots , 25 \right\}$ such that the sum of any two (not necessarily distinct) elements of $S$ is never an element of $S.$ What is the maximum number of elements $S$ may contain?

$\textbf{(A)}\ 12 \qquad\textbf{(B)}\ 13 \qquad\textbf{(C)}\ 14 \qquad\textbf{(D)}\ 15 \qquad\textbf{(E)}\ 16$

Solution 1 (Pigeonhole Principle)

Let $M$ be the largest number in $S$. We categorize numbers $\left\{ 1, 2, \ldots , M-1 \right\}$ (except $\frac{M}{2}$ if $M$ is even) into $\left\lfloor \frac{M-1}{2} \right\rfloor$ groups, such that the $i$th group contains two numbers $i$ and $M-i$.

Recall that $M \in S$ and the sum of two numbers in $S$ cannot be equal to $M$, and the sum of numbers in each group above is equal to $S$. Thus, each of the above $\left\lfloor \frac{M-1}{2} \right\rfloor$ groups can have at most one number in $S$. Therefore, \begin{align*} |S| & \leq 1 + \left\lfloor \frac{M-1}{2} \right\rfloor \\ & \leq 1 + \left\lfloor \frac{25}{2} \right\rfloor \\ & = 13. \end{align*}

Next, we construct an instance of $S$ with $|S| = 13$. Let $S = \left\{ 13, 14, \ldots , 25 \right\}$. Thus, this set is feasible. Therefore, the most number of elements in $S$ is $\boxed{\textbf{(B) }13}$.

~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)

Solution 2 (Pigeonhole v2)

We construct a possible subset $S$ with $13$ elements by including all odd integers from $1$ to $25$, inclusive. $S=\left\{ 1, 3, 5, \cdots , 25 \right\}$. The sum of any $2$ elements is even, and thus cannot be an element of $S$.

To show that $S$ cannot have more than $13$ elements, assume for sake of contradiction that $|S| \geq 14$. Let $S=\left\{ x_1, x_2, \cdots , x_n \right\}$ where $n \geq 14$ and $x_1 < x_2 < \cdots < x_n$. Because the sums of any $2$ (not necessarily distinct) elements do not appear in $S$, $x_1+x_i$ is not an element of $S$ for all $1 \leq i \leq n$. So, $x_1, x_2, \cdots , x_n , x_1+x_1, x_1+x_2, \cdots , x_1+x_n$ are all distinct integers. Let these integers be elements of the set $T$. $|T|=2n$, and because $n \geq 14$, $|T| \geq 28$. But all elements of $T$ must be $\geq x_1$ and $\leq x_1+x_n \leq x_1+25$, leaving only 26 possible values for the elements in $T$. By the Pigeonhole Principle, the elements cannot be distinct, and we have a contradiction.

Thus, $\boxed{\textbf{(B) }13}$ is the maximum possible size of $S$.

~starwars101

Solution 3 (Intuitive and Fast)

Notice how \( 24 + 25 > 25 \), \( 23 + 24 > 25 \), and this continues backward until \( n + n+1 > 25 \). We then see that \( 2n+1 > 25 \rightarrow 2n > 24 \rightarrow n > 12 \).

Thus the elements in the set must have the property \( n > 12 : n \in \mathbb{Z}^+ \) and therefore our set is \( \{13, 14, 15, \dots, 25\} \) in which there is \( 25 - 13 + 1 \Rightarrow \) $\boxed{\textbf{(B) }13}$ elements.

~Pinotation

Video Solution

https://youtu.be/_K29sOequlY

~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)

Video Solution by Interstigation

https://youtu.be/in3N3Os5kGw

Video Solution by TheBeautyofMath

https://youtu.be/Mi2AxPhnRno?t=1056

~IceMatrix

See Also

2025 AMC 10A Q21/AMC 12A Q15

2022 AMC 10B (Problems • Answer Key • Resources)
Preceded by
Problem 13 		Followed by
Problem 15
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

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

Retrieved from "https://wiki.aopstest.com/wiki/index.php?title=2022_AMC_10B_Problems/Problem_14&oldid=268064"