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

Difference between revisions of "2022 AMC 10B Problems/Problem 14"

m (→‎Solution (Pigeonhole Principle))
(→‎Solution 4 (Pigeonhole v2))
(23 intermediate revisions by 10 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 <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) 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?
−
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)==
+
<math>\textbf{(A)}\ 12 \qquad\textbf{(B)}\ 13 \qquad\textbf{(C)}\ 14 \qquad\textbf{(D)}\ 15 \qquad\textbf{(E)}\ 16</math>
  
−
Denote by <math>M</math> the largest number in <math>S</math>.
+
==Solution 1 (Pigeonhole Principle)==
−
We categorize numbers <math>\left\{ 1, 2, \ldots , M-1 \right\}</math> (except <math>\frac{M}{2}</math> if <math>M</math> is even) into <math>\left\lfloor \frac{M-1}{2} \right\\rfloor</math> groups, such that the <math>i</math>th group contains two numbers <math>i</math> and <math>M-i</math>.
+
Let <math>M</math> be the largest number in <math>S</math>.
 +
We categorize numbers <math>\left\{ 1, 2, \ldots , M-1 \right\}</math> (except <math>\frac{M}{2}</math> if <math>M</math> is even) into <math>\left\lfloor \frac{M-1}{2} \right\rfloor</math> groups, such that the <math>i</math>th group contains two numbers <math>i</math> and <math>M-i</math>.
  
−
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 <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>\left\lfloor \frac{M-1}{2} \right\rfloor</math> groups can have at most one number in <math>S</math>.
 
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>
Line 23: Line 23:
 
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 <math>S</math> is
−
<math>\boxed{\textbf{(B) 13}}</math>.
+
<math>\boxed{\textbf{(B) }13}</math>.
  
 
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
 
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
  
 
==Solution 2==
 
==Solution 2==
−
We know that two odd numbers sum to an even number, so we can easily say that odd numbers <math>1-25</math> can be included in the list, making for <math>13</math> elements. But, how do we know we can't include even numbers for a higher element value? Well, to get a higher element value than <math>13</math>, odd numbers as well as even numbers would have to be included in the list (since there are only <math>12</math> even numbers from <math>1-25</math>, and many of those even numbers are the sum of even numbers). However, for every even value we add to our odd list, we have to take away an odd number because there are either two odd numbers that sum to that even value, or that even value and another odd number will sum to an odd number later in the list. So, <math>\boxed{\textbf{(B) 13}}</math> elements is the highest we can go.
+
We know that two odd numbers sum to an even number, so we can easily say that odd numbers <math>1-25</math> can be included in the list, making for <math>13</math> elements. But, how do we know we can't include even numbers for a higher element value? Well, to get a higher element value than <math>13</math>, odd numbers as well as even numbers would have to be included in the list (since there are only <math>12</math> even numbers from <math>1-25</math>, and many of those even numbers are the sum of even numbers). However, for every even value we add to our odd list, we have to take away an odd number because there are either two odd numbers that sum to that even value, or that even value and another odd number will sum to an odd number later in the list. So, <math>\boxed{\textbf{(B) }13}</math> elements is the highest we can go.
 +
 
 +
== Solution 3 ==
 +
 
 +
The smallest sum of a number <math>a + b</math> where <math>b \geq a</math> is <math>a + a = 2a</math> as we are using the smallest value of <math>b</math>. Using this, we can say that if <math>12</math> were an element of <math>S</math>, then one of the sums (the smallest) would be <math>12 + 12 = 24 < 25</math>. Thus <math>13</math> must be the smallest element. So the largest amount of elements that could be in <math>S</math> is the list of numbers from <math>13</math> to <math>25</math> as they all work. Because it is inclusive we have, <math>25 - 13 + 1 =
 +
\boxed{\textbf{(B) }13}</math>.
 +
 
 +
~ Wiselion :)
 +
 
 +
== Solution 4 (Pigeonhole v2) ==
 +
 
 +
We construct a possible subset <math>S</math> with <math>13</math> elements by including all odd integers from <math>1</math> to <math>25</math>, inclusive. <math>S=\left\{ 1, 3, 5, \cdots , 25 \right\}</math>. The sum of any <math>2</math> elements is even, and thus cannot be an element of <math>S</math>.
 +
 
 +
To show that <math>S</math> cannot have more than <math>13</math> elements, assume for sake of contradiction that <math>|S| \geq 14</math>. Let <math>S=\left\{ x_1, x_2, \cdots , x_n \right\}</math> where <math>n \geq 14</math> and <math>x_1 < x_2 < \cdots < x_n</math>. Because the sums of any <math>2</math> (not necessarily distinct) elements do not appear in <math>S</math>, <math>x_1+x_i</math> is not an element of <math>S</math> for all <math>1 \leq i \leq n</math>. So, <math>x_1, x_2, \cdots , x_n , x_1+x_1, x_1+x_2, \cdots , x_1+x_n</math> are all distinct integers. Let these integers be elements of the set <math>T</math>. <math>|T|=2n</math>, and because <math>n \geq 14</math>, <math>|T| \geq 28</math>. But all elements of <math>T</math> must be <math>\geq x_1</math> and <math>\leq x_1+x_n \leq x_1+25</math>, leaving only 26 possible values for the elements in <math>T</math>. By the Pigeonhole Principle, the elements cannot be distinct, and we have a contradiction.
 +
 
 +
Thus, <math> \boxed{\textbf{(B) }13}</math> is the maximum possible size of <math>S</math>.
 +
 
 +
~starwars101
 +
 
 +
== Solution 5 (solution 2 with a deeper explanation. For if you felt stuck at the start) ==
 +
 
 +
The first element of subset <math>S</math> must be <math>1</math>. Nothing between <math>1</math> and <math>25</math> can possibly add up to <math>1</math>, so that's your first number. Since you included <math>1</math>, you cannot include <math>2</math> and must instead include <math>3</math>. Now that you have <math>1</math> and <math>3</math>, you cannot include <math>4</math> or <math>6</math>, so you include <math>5</math>. Including <math>5</math> rules out <math>8</math> and <math>10</math>. So the next numbers to include are <math>7</math> and <math>9</math>. By this point, it's evident that you're going by odds. But will this pattern will continue?
 +
 
 +
Since you started out with <math>1</math> and then <math>3</math>, you could only ever use those odd numbers to create even numbers. Odd plus odd is never odd, so the next smallest number <math>S</math> can contain will always be the next smallest odd number.
 +
 
 +
 
 +
So now you have the odds from <math>1</math> to <math>25</math>. You might realize quickly that that is <math>\textbf{13}</math> elements, but if you don't, you can convert them to the evens <math>2</math> to <math>26</math>. By halving each term, you have integers <math>1</math> to <math>13</math>, so it's obvious now that the answer is <math> \boxed{\textbf{(B)} 13}</math>
 +
 
 +
~mihikamishra
  
 
==Video Solution==
 
==Video Solution==
Line 35: Line 63:
  
 
~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 ==
 
== See Also ==
 
{{AMC10 box|year=2022|ab=B|num-b=13|num-a=15}}
 
{{AMC10 box|year=2022|ab=B|num-b=13|num-a=15}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 11:28, 24 August 2024

Problem

Suppose that $S$ is a subset of $\left\{ 1, 2, 3, \cdots , 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

We know that two odd numbers sum to an even number, so we can easily say that odd numbers $1-25$ can be included in the list, making for $13$ elements. But, how do we know we can't include even numbers for a higher element value? Well, to get a higher element value than $13$, odd numbers as well as even numbers would have to be included in the list (since there are only $12$ even numbers from $1-25$, and many of those even numbers are the sum of even numbers). However, for every even value we add to our odd list, we have to take away an odd number because there are either two odd numbers that sum to that even value, or that even value and another odd number will sum to an odd number later in the list. So, $\boxed{\textbf{(B) }13}$ elements is the highest we can go.

Solution 3

The smallest sum of a number $a + b$ where $b \geq a$ is $a + a = 2a$ as we are using the smallest value of $b$. Using this, we can say that if $12$ were an element of $S$, then one of the sums (the smallest) would be $12 + 12 = 24 < 25$. Thus $13$ must be the smallest element. So the largest amount of elements that could be in $S$ is the list of numbers from $13$ to $25$ as they all work. Because it is inclusive we have, $25 - 13 + 1 = \boxed{\textbf{(B) }13}$.

~ Wiselion :)

Solution 4 (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 5 (solution 2 with a deeper explanation. For if you felt stuck at the start)

The first element of subset $S$ must be $1$. Nothing between $1$ and $25$ can possibly add up to $1$, so that's your first number. Since you included $1$, you cannot include $2$ and must instead include $3$. Now that you have $1$ and $3$, you cannot include $4$ or $6$, so you include $5$. Including $5$ rules out $8$ and $10$. So the next numbers to include are $7$ and $9$. By this point, it's evident that you're going by odds. But will this pattern will continue?

Since you started out with $1$ and then $3$, you could only ever use those odd numbers to create even numbers. Odd plus odd is never odd, so the next smallest number $S$ can contain will always be the next smallest odd number.


So now you have the odds from $1$ to $25$. You might realize quickly that that is $\textbf{13}$ elements, but if you don't, you can convert them to the evens $2$ to $26$. By halving each term, you have integers $1$ to $13$, so it's obvious now that the answer is $\boxed{\textbf{(B)} 13}$

~mihikamishra

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

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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

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