Difference between revisions of "2024 AMC 10A Problems/Problem 20"
(→Problem) |
m (Fixed the answer format in solution 2) |
||
| (14 intermediate revisions by 6 users not shown) | |||
| Line 1: | Line 1: | ||
==Problem== | ==Problem== | ||
| − | Let <math>S</math> be a subset of <math>\{1, 2, 3, \dots, 2024\}</math> such that the following two conditions hold: | + | Let <math>S</math> be a subset of <math>\{1, 2, 3, \dots, 2024\}</math> such that the following two conditions hold: <math>\linebreak</math> |
| − | + | * If <math>x</math> and <math>y</math> are distinct elements of <math>S</math>, then <math>|x-y| > 2</math> <math>\linebreak</math> | |
| − | + | * If <math>x</math> and <math>y</math> are distinct odd elements of <math>S</math>, then <math>|x-y| > 6</math>. <math>\linebreak</math> | |
What is the maximum possible number of elements in <math>S</math>? | What is the maximum possible number of elements in <math>S</math>? | ||
| Line 27: | Line 27: | ||
If n = 2 was optimal, then choose it, then the set of usable numbers in <math>S</math> becomes 5 through 2024. We can transform the usable set of <math>S</math> to <math>Q</math> where <math>Q</math> contains the numbers 1 through 2020. Because we assumed n = 2 was optimal, we can choose n = 2 for the set <math>Q</math> too. Because every element in <math>Q</math> is 4 below the elements of <math>S</math>, choosing 2 in <math>Q</math> would mean choosing 6 in set <math>S</math>. By induction we see that our list would be {2,6,10,14,18,.....2022} which only gives 506 elements which is sub-optimal. Therefore, we can conclude that n = 1 is optimal, and we proceed as the solution above. | If n = 2 was optimal, then choose it, then the set of usable numbers in <math>S</math> becomes 5 through 2024. We can transform the usable set of <math>S</math> to <math>Q</math> where <math>Q</math> contains the numbers 1 through 2020. Because we assumed n = 2 was optimal, we can choose n = 2 for the set <math>Q</math> too. Because every element in <math>Q</math> is 4 below the elements of <math>S</math>, choosing 2 in <math>Q</math> would mean choosing 6 in set <math>S</math>. By induction we see that our list would be {2,6,10,14,18,.....2022} which only gives 506 elements which is sub-optimal. Therefore, we can conclude that n = 1 is optimal, and we proceed as the solution above. | ||
| − | + | -weihou0 | |
| + | |||
| + | ==Solution 2== | ||
| + | Notice that we can first place odd numbers, then place even numbers between each pair. We can start at <math>1</math> and continue from there. Realize that the smallest number <math>k</math> such that <math>kx+1</math> reproduces odd number is <math>8</math>. The next ones are <math>10, 12, 14</math>. We can proceed to find the number of numbers in this particular sequence. From the equation <math>8x+1=2023</math>, we get that <math>x \leq 252.875</math> works, so this means there is 253 solutions. Looking at <math>1,2,3,4,5,6,7,9</math> we can see that there could only be 1 possible number between each pair, yielding <math>252+253=505</math>. Then see that we can fit two more into the number count since the set <math>2017</math> to <math>2024</math> can fit two evens. Now this means <math>A</math> and <math>B</math> don’t work. Now test out <math>10x+1</math>. Using the same method, we get that <math>608</math> is the maximum number in the set. Everything above <math>x=10</math> doesn’t work, as we can split it down into smaller subgroups, so the answer is <math>\boxed{\textbf{(C) }608}</math>. | ||
| + | |||
| + | ~EaZ_Shadow | ||
| + | |||
| + | |||
| + | == Video Solution by Power Solve == | ||
| + | https://www.youtube.com/watch?v=NZ0SBMqeAfg | ||
== Video Solution by Pi Academy == | == Video Solution by Pi Academy == | ||
| − | |||
https://youtu.be/fW7OGWee31c?si=oq7toGPh2QaksLHE | https://youtu.be/fW7OGWee31c?si=oq7toGPh2QaksLHE | ||
| − | + | ==Video Solution by SpreadTheMathLove== | |
| + | https://www.youtube.com/watch?v=6SQ74nt3ynw | ||
==See also== | ==See also== | ||
{{AMC10 box|year=2024|ab=A|num-b=19|num-a=21}} | {{AMC10 box|year=2024|ab=A|num-b=19|num-a=21}} | ||
{{MAA Notice}} | {{MAA Notice}} | ||
Latest revision as of 21:06, 17 November 2024
Contents
Problem
Let 
be a subset of 
such that the following two conditions hold: 
- If
and 
are distinct elements of 
, then 
- If and are distinct odd elements of , then
.
and 
are distinct elements of 
. What is the maximum possible number of elements in ?
Video Solution by Scholars Foundation
https://www.youtube.com/watch?v=FKOqZau--5w&t=1s
Solution 1
All lists are organized in ascending order:
By listing out the smallest possible elements of subset 
we can find that subset starts with 
It is easily noticed that the elements of the subset "loop around" every 3 elements, specifically adding 10 each time. This means that there will be 
or 
whole loops in the subset implying that there will be 
elements in S. However, we have undercounted, as we did not count the remainder that resulted from 
With a remainder of 
we can fit 
more elements into the subset namely 
and 
resulting in a total of 
or 
elements in subset .
NOTE:
To prove that this is the best we can do, consider adding each element one by one, for the first element, say n. If n is greater than 2, we can choose n - 2 which is always better. Therefore, n = 1 or n = 2.
If n = 2 was optimal, then choose it, then the set of usable numbers in becomes 5 through 2024. We can transform the usable set of to 
where contains the numbers 1 through 2020. Because we assumed n = 2 was optimal, we can choose n = 2 for the set too. Because every element in is 4 below the elements of , choosing 2 in would mean choosing 6 in set . By induction we see that our list would be {2,6,10,14,18,.....2022} which only gives 506 elements which is sub-optimal. Therefore, we can conclude that n = 1 is optimal, and we proceed as the solution above.
-weihou0
Solution 2
Notice that we can first place odd numbers, then place even numbers between each pair. We can start at 
and continue from there. Realize that the smallest number 
such that 
reproduces odd number is 
. The next ones are 
. We can proceed to find the number of numbers in this particular sequence. From the equation 
, we get that 
works, so this means there is 253 solutions. Looking at 
we can see that there could only be 1 possible number between each pair, yielding 
. Then see that we can fit two more into the number count since the set 
to 
can fit two evens. Now this means 
and 
don’t work. Now test out 
. Using the same method, we get that 
is the maximum number in the set. Everything above 
doesn’t work, as we can split it down into smaller subgroups, so the answer is .
~EaZ_Shadow
Video Solution by Power Solve
https://www.youtube.com/watch?v=NZ0SBMqeAfg
Video Solution by Pi Academy
https://youtu.be/fW7OGWee31c?si=oq7toGPh2QaksLHE
Video Solution by SpreadTheMathLove
https://www.youtube.com/watch?v=6SQ74nt3ynw
See also
| 2024 AMC 10A (Problems • Answer Key • Resources) | ||
| Preceded by Problem 19 |
Followed by Problem 21 | |
| 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. 
