Difference between revisions of "2024 AMC 10A Problems/Problem 20"

Revision as of 13:13, 10 November 2024

Problem

Let $S$ be a subset of $\{1, 2, 3, \dots, 2024\}$ such that the following two conditions hold: $\linebreak$

If $x$ and $y$ are distinct elements of $S$ , then $|x-y| > 2$ $\linebreak$
If $x$ and $y$ are distinct odd elements of $S$ , then $|x-y| > 6$ . $\linebreak$

What is the maximum possible number of elements in $S$ ?

$\textbf{(A) }436 \qquad \textbf{(B) }506 \qquad \textbf{(C) }608 \qquad \textbf{(D) }654 \qquad \textbf{(E) }675 \qquad$

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 $S,$ we can find that subset $S$ starts with $\{1, 4, 8, 11, 14, 18, 21, 24, 28, 31, \dots\}.$ 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 $2024/10$ or $202R4$ whole loops in the subset $S,$ implying that there will be $202*3 = 606$ elements in S. However, we have undercounted, as we did not count the remainder that resulted from $2024/10$ $.$ With a remainder of $4,$ we can fit $2$ more elements into the subset $S,$ namely $2021$ and $2024,$ resulting in a total of $606+2$ or $\boxed{\textbf{(C) }608}$ elements in subset $S$ .

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 $S$ becomes 5 through 2024. We can transform the usable set of $S$ to $Q$ where $Q$ contains the numbers 1 through 2020. Because we assumed n = 2 was optimal, we can choose n = 2 for the set $Q$ too. Because every element in $Q$ is 4 below the elements of $S$ , choosing 2 in $Q$ would mean choosing 6 in set $S$ . 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$ (Error compiling LaTeX. Unknown error_msg)1 $and continue from there. Realize that the smallest number$ k $such that$ kx+1 $reproduces odd number is$ 8 $. The next ones are$ 10, 12, 14 $. We can proceed to find the number of numbers in this particular sequence. From the equation$ 8x+1=2023 $, we get that$ x \leq 252.875 $works, so this means there is 253 solutions. Looking at$ 1,2,3,4,5,6,7,9 $we can see that there could only be 1 possible number between each pair, yielding$ 252+253=505 $. Then see that we can fit two more into the number count since the set$ 2017 $to$ 2024 $can fit two evens. Now this means$ A $and$ B $don’t work. Now test out$ 10x+1 $. Using the same method, we get that$ 608 $is the maximum number in the set. Everything above$ x=10 $doesn’t work, as we can split it down into smaller subgroups, so the answer is$ \boxed{\boxed{\textbf{C}}}$. ~EaZ_Shadow

Video Solution by Pi Academy

https://youtu.be/fW7OGWee31c?si=oq7toGPh2QaksLHE

@@ 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.
-$-weihou0
+<math>-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{\boxed{\textbf{C}}}$.
+~EaZ_Shadow
 == Video Solution by Pi Academy ==

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

Page

Toolbox

Search