|
|
| (14 intermediate revisions by 9 users not shown) |
| Line 1: |
Line 1: |
| A set of numbers is called <imath>sum</imath>-<imath>free</imath> if whenever <imath>x</imath> and <imath>y</imath> are (not necessarily distinct) elements of the set, <imath>x+y</imath> is not an element of the set. For example, <imath>\{1,4,6\}</imath> and the empty set are sum-free, but <imath>\{2,4,5\}</imath> is not. What is the greatest possible number of elements in a sum-free subset of <imath>\{1,2,3,...,20\}</imath>?
| | #redirect [[2025 AMC 12A Problems/Problem 15]] |
| | |
| <imath>\textbf{(A) } 8 \qquad\textbf{(B) } 9 \qquad\textbf{(C) } 10 \qquad\textbf{(D) } 11 \qquad\textbf{(E) } 12</imath>
| |
| | |
| ==Solution 1==
| |
| Let our subset be <imath>\{11,12,13,...,20\}.</imath> If we add any one element from the set <imath>\{1,2,3,...,10\},</imath> we will have to remove at least one element from our current subset. Hence, the size of our set cannot exceed <imath>\boxed{\text{(C) }10}.</imath>
| |
| | |
| ~Tacos_are_yummy_1
| |
| | |
| ==Solution 2==
| |
| Let our subset be <imath>\{1,3,5,...,19\}.</imath> Since odd numbers + odd numbers will always sum to an even number, this subset holds true. Leo, the addition of any even number will result in a violation of the rule, so the maximum number of elements is <imath>\boxed{\text{(C) }10}.</imath>
| |
| | |
| ~Kevin Wang
| |
| | |
| ==Solution 3 (Those who know)==
| |
| I'm kinda surprised that this question is just the copy-and-paste version of 2022 10B Problem 14. This problem is easier yet it's at problem 21. Nice problem quality you got there, huh, just adding a fancy definition, and yay, you got a brand new problem!
| |
| | |
| https://artofproblemsolving.com/wiki/index.php?title=2022_AMC_10B_Problems/Problem_14
| |
| | |
| ~metrixgo
| |
| | |
| I litterly remember the problem from 2022. If anything, this one's easier. Not complaining though.
| |
| | |
| Its literally just the number of elements if you only put the odd numbers in like what this should’ve been problem 10 not that semicircle problem
| |
| ~[[User:grogg007|grogg007]]
| |
| | |
| Same! When reaching this question, I immediately thought of the 2022 question. Thanks for pointing out the old version, though!
| |
| | |
| ~Leon S
| |
| | |
| frfr I thought so too
| |
| ~BOTNATE
| |
| | |
| bruh i recognized it too but i didn't realize the last number was 20 (well obviously i did but i mean like its even) so then i included 10 in my set (10,11,....20) so i picked 11 instead of 10
| |
| ~PerseverePlayer
| |
| Bro are we seriosly starting a chat on a official AOPS answer key page. bruh :/
| |
| ~AbirAwate
| |
| | |
| ==Solution 4 (More Rigorous)==
| |
| Constructions work for <imath>10</imath>, such as <imath>\{11,12,13,...,20\}</imath> or <imath>\{1,3,5,...,19\}</imath>.
| |
| | |
| Proof that 11+ don't work: assume that there are 11 or more numbers in the set. That means that there are less than or equal to 9 numbers in the set not included.
| |
| | |
| Take the smallest number and look at the differences with the other numbers. With at least 10 other numbers, there are at least 10 other differences with the other numbers. However, since all of them are distinct and we are looking at the smallest number, then all of these differences are distinct. Additionally, all these differences are positive and less than 20, so we have that they are all in the set as well. Thus we have a contradiction because we need at least 10 other differences that aren't included in the set, but there are less than or equal to 9 numbers not included in the set.
| |
| | |
| Thus we have proven that $\boxed{\text{(C) }10} is the max.
| |
| | |
| ~Ant_Eater
| |
| | |
| == Video Solution (In 1 Min) ==
| |
| https://youtu.be/V_zh78Ae8xw?si=D8dEsX4ST3JORj6x ~ Pi Academy
| |
| | |
| ==Video Solution==
| |
| https://youtu.be/gWSZeCKrOfU
| |
| | |
| ~MK
| |
| | |
| ==Video Solution by OmegaLearn==
| |
| https://youtu.be/GgNQ2yDGIRg
| |
| | |
| | |
| ==See also==
| |
| {{AMC10 box|year=2025|ab=A|num-b=20|num-a=22}}
| |
| {{AMC12 box|year=2025|ab=A|num-b=17|num-a=19}}
| |
| {{MAA Notice}}
| |
