|
|
| 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 (Those who know)==
| |
| This problem is essentially the same as 2022 AMC 10B Problem 14.
| |
| | |
| https://artofproblemsolving.com/wiki/index.php?title=2022_AMC_10B_Problems/Problem_14
| |
| | |
| ~metrixgo
| |
| | |
| ==Solution 2 ==
| |
| Constructions work for <imath>10</imath>, such as <imath>\{11,12,13,...,20\}</imath> or <imath>\{1,3,5,...,19\}</imath>.
| |
| | |
| Take the smallest number and look at the differences with the other numbers. With <imath>n-1</imath> other numbers, there are at least <imath>n-1</imath> 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 <imath>n + n - 1 \leq 20 </imath>, so <imath>n \leq 10.5 </imath>.
| |
| | |
| Thus we have proven that <imath>\boxed{\text{(C) }10}</imath> is the max.
| |
| | |
| ~Ant_Eater
| |
| | |
| ==Solution 3==
| |
| Constructions work for <imath>10</imath> as seen above.
| |
| | |
| We claim <imath>10</imath> is the maximum. Let <imath>n</imath> be the greatest element of our subset. Pair up the elements less than <imath>n</imath> of the given set so that <imath>k</imath> is with <imath>n-k</imath>. Note that only one element in each pair can be in the subset, and we have <imath>\left\lfloor\frac{n-1}2\right\rfloor</imath> pairs (since for even <imath>n</imath>, <imath>\frac{n}2</imath> can’t be in the subset). Therefore, the subset has at most <imath>1+\left\lfloor\frac{n-1}2\right\rfloor</imath> elements. This function is nondecreasing, so we can plug in <imath>20</imath> and find that the sum-free subset has at most <imath>\boxed{\text{(C) }10}</imath> elements.
| |
| | |
| ~Waddles2010
| |
| | |
| | |
| == Video Solution ==
| |
| https://youtu.be/V_zh78Ae8xw?si=D8dEsX4ST3JORj6x ~ Pi Academy
| |
| | |
| ==Video Solution==
| |
| https://youtu.be/gWSZeCKrOfU
| |
| | |
| ~MK
| |
| | |
| ==Video Solution by OmegaLearn==
| |
| https://youtu.be/GgNQ2yDGIRg
| |
| | |
| ==Video Solution by SpreadTheMathLove==
| |
| https://www.youtube.com/watch?v=dAeyV60Hu5c
| |
| ==See also==
| |
| 2022 AMC10B problem14
| |
| {{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}}
| |
