Difference between revisions of "2022 AMC 10B Problems/Problem 14"
Starwars101 (talk | contribs) m (added conclusion to solution 4) |
Starwars101 (talk | contribs) m (→Solution 4 (Pigeonhole v2)) |
||
Line 41: | Line 41: | ||
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>. | 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> | + | 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 \geq i \geq 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>. | Thus, <math> \boxed{\textbf{(B) }13}</math> is the maximum possible size of <math>S</math>. |
Revision as of 00:52, 19 October 2023
Contents
[hide]Problem
Suppose that is a subset of
such that the sum of any two (not necessarily distinct) elements of
is never an element of
What is the maximum number of elements
may contain?
Solution 1 (Pigeonhole Principle)
Let be the largest number in
.
We categorize numbers
(except
if
is even) into
groups, such that the
th group contains two numbers
and
.
Recall that and the sum of two numbers in
cannot be equal to
, and the sum of numbers in each group above is equal to
. Thus, each of the above
groups can have at most one number in
.
Therefore,
Next, we construct an instance of with
.
Let
.
Thus, this set is feasible.
Therefore, the most number of elements in
is
.
~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 can be included in the list, making for
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
, odd numbers as well as even numbers would have to be included in the list (since there are only
even numbers from
, 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,
elements is the highest we can go.
Solution 3
The smallest sum of a number where
is
as we are using the smallest value of
. Using this, we can say that if
were an element of
, then one of the sums (the smallest) would be
. Thus
must be the smallest element. So the largest amount of elements that could be in
is the list of numbers from
to
as they all work. Because it is inclusive we have,
.
~ Wiselion :)
Solution 4 (Pigeonhole v2)
We construct a possible subset with
elements by including all odd integers from
to
, inclusive.
. The sum of any
elements is even, and thus cannot be an element of
.
To show that cannot have more than
elements, assume for sake of contradiction that
. Let
where
and
. Because the sums of any
(not necessarily distinct) elements do not appear in
,
is not an element of
for all
. So,
are all distinct integers. Let these integers be elements of the set
.
, and because
,
. But all elements of
must be
and
, leaving only 26 possible values for the elements in
. By the Pigeonhole Principle, the elements cannot be distinct, and we have a contradiction.
Thus, is the maximum possible size of
.
~starwars101
Video Solution
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
Video Solution by Interstigation
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.