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

Revision as of 23:25, 18 October 2023

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 $a$ . Using this we can say that if $12$ were an element of $S$ , then one of the sum (the smallest) would be $24 < 25$ . Thus $13$ must be the smallest element. So the largest amount of number is the list of number from $13$ to $25$ as they all work. Because it is inclusive we have, $25 - 13 + 1 = \boxed{\textbf{(B)}26}$ .

~ Wiselion :)

Video Solution

https://youtu.be/_K29sOequlY

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

Video Solution by Interstigation

https://youtu.be/in3N3Os5kGw

@@ Line 29: / Line 29: @@
 ==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.
+== 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>a</math>. Using this we can say that if <math>12</math> were an element of <math>S</math>, then one of the sum (the smallest) would be <math>24 < 25</math>. Thus <math>13</math> must be the smallest element. So the largest amount of number is the list of number 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)}26}</math>.
+~ Wiselion :)
 ==Video Solution==

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

Page

Toolbox

Search