AMC 10 · 2024 · #20
Grade 6 countingnumber-theoryProblem
Let S be a subset of {1,2,3,…,2024} such that the following two conditions hold:
If x and y are distinct elements of S, then ∣x−y∣>2.
If x and y are distinct odd elements of S, then ∣x−y∣>6.
What is the maximum possible number of elements in S?
Pick an answer.
AMC 10 2024 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.
Try it yourself first — the explanation is most useful after you’ve attempted it.
Toolkit + CCSS Solution
Understand
Restated: Pick as many numbers as possible from $\{1, 2, 3, \dots, 2024\}$ so that any two chosen numbers differ by more than $2$, and any two chosen odd numbers differ by more than $6$. What is the largest size such a set $S$ can have?
Givens: $S \subseteq \{1, 2, 3, \dots, 2024\}$; For any two distinct $x, y \in S$: $|x - y| > 2$ (so $|x - y| \ge 3$); For any two distinct odd $x, y \in S$: $|x - y| > 6$ (so $|x - y| \ge 8$, because the difference of two odds is even); Answer choices: (A) $436$, (B) $506$, (C) $608$, (D) $654$, (E) $675$
Unknowns: The maximum number of elements $|S|$
Understand
Restated: Pick as many numbers as possible from $\{1, 2, 3, \dots, 2024\}$ so that any two chosen numbers differ by more than $2$, and any two chosen odd numbers differ by more than $6$. What is the largest size such a set $S$ can have?
Givens: $S \subseteq \{1, 2, 3, \dots, 2024\}$; For any two distinct $x, y \in S$: $|x - y| > 2$ (so $|x - y| \ge 3$); For any two distinct odd $x, y \in S$: $|x - y| > 6$ (so $|x - y| \ge 8$, because the difference of two odds is even); Answer choices: (A) $436$, (B) $506$, (C) $608$, (D) $654$, (E) $675$
Plan
Primary tool: #9 Solve an Easier Related Problem
Secondary: #5 Look for a Pattern
$2024$ is too big to attack head-on, so Tool #9 (Easier Related Problem) says: build the densest legal set greedily from $1$ upward on a small slice and see what shape it has. As soon as the construction reaches $1, 4, 8, 11, 14, 18, \dots$ Tool #5 (Look for a Pattern) takes over — the consecutive gaps cycle $+3, +4, +3, +3, +4, +3, \dots$, which is the same as saying "3 chosen numbers every 10 integers." Once that block of $10$ is verified, the full count on $[1, 2024]$ is just three short arithmetic-progression counts. No heavier algebra is needed, and the greedy construction also doubles as a proof of optimality (every legal denser packing would violate one of the two gap rules).
Execute — Answer: C
6.EE.B.8 Step 1 - Restate the two gap rules in usable form.
- Rule 1 says any two chosen integers differ by at least $3$.
- Rule 2 says any two chosen odd integers differ by at least $8$ — note that the difference of two odd numbers is always even, so "more than $6$" is the same as "at least $8$." Both bounds will drive the greedy build.
💡 Translating "$|x-y| > 2$" into "$|x-y| \ge 3$" is Grade 6 inequality reading: strict inequality on integers means the next integer up.
5.OA.B.3 Step 2 - Greedy-construct the densest legal set starting from $1$.
- At each step pick the smallest integer that does not violate either rule.
- The first few choices: take $1$ (odd).
- Next must be $\ge 4$, take $4$.
- Next must be $\ge 7$ from the $4$-rule; $7$ is odd and $|7 - 1| = 6$ violates the odd rule, so skip $7$ and take $8$.
- Next must be $\ge 11$; $11$ is odd, $|11 - 1| = 10 \ge 8$, so take $11$.
- Continue: $14, 18, 21, 24, 28, 31, \dots$
💡 Greedy on a small slice is the Grade 5 "generate the next term by a rule" move — and "smallest legal next number" is exactly the densest packing.
5.OA.B.3 Step 3 - Read the pattern out of the gap sequence.
- The consecutive differences are $3, 4, 3, 3, 4, 3, 3, 4, 3, \dots$, which groups as a repeating block $(+3, +4, +3)$ of total length $3 + 4 + 3 = 10$.
- So three numbers are chosen out of every $10$ consecutive integers, and after one block the pattern shifts by $10$: $a_{n+3} = a_n + 10$.
💡 A repeating gap block means three interleaved arithmetic progressions with common difference $10$ — the Grade 5 "identify the rule, then jump to the $k$-th term" idea.
6.EE.A.2 Step 4 - Split $S$ into three arithmetic progressions.
- The starting triple $(1, 4, 8)$ plus the shift $a_{n+3} = a_n + 10$ gives three families inside $\{1, \dots, 2024\}$.
- Family I (odd, the only odd family): $1 + 10k$.
- Family II: $4 + 10k$.
- Family III: $8 + 10k$, all with $k \ge 0$.
💡 Naming the three families with a single index $k$ is the Grade 6 "write an expression with a variable" move that turns counting into solving an inequality.
6.EE.B.8 Step 5 - Count the legal $k$ in each family by solving an inequality.
- Family I needs $1 + 10k \le 2024$, so $k \le 202.3$, giving $k \in \{0, \dots, 202\}$ — that is $203$ terms.
- Family II needs $4 + 10k \le 2024$, so $k \le 202$, again $203$ terms.
- Family III needs $8 + 10k \le 2024$, so $k \le 201.6$, giving $k \in \{0, \dots, 201\}$ — that is $202$ terms.
💡 Each family count is the same Grade 6 inequality-counting drill: how many non-negative integers $k$ satisfy $A + 10k \le 2024$?
5.OA.B.3 Step 6 - Add the three counts.
- The three families are pairwise disjoint by construction (they cover different residues $1, 4, 8 \pmod{10}$), so total $= 203 + 203 + 202$.
- Verify the rules one last time: any two members of Family I differ by a positive multiple of $10 \ge 8$ (odd rule holds); Families II and III are all even, so the odd rule is vacuous there; and the minimum gap across all of $S$ is $\min(3, 4, 3) = 3$ (general rule holds).
- The construction is legal, and since we always took the smallest legal next integer, no denser legal set exists.
💡 Disjoint-by-residue counts add cleanly — exactly the Grade 5 "count by groups, then add" structure.
6.EE.B.8 Restate the two gap rules in usable form. Rule 1 says any two chosen integers di 5.OA.B.3 Greedy-construct the densest legal set starting from $1$. At each step pick the 5.OA.B.3 Read the pattern out of the gap sequence. The consecutive differences are $3, 4, 6.EE.A.2 Split $S$ into three arithmetic progressions. The starting triple $(1, 4, 8)$ pl 6.EE.B.8 Count the legal $k$ in each family by solving an inequality. Family I needs $1 + 5.OA.B.3 Add the three counts. The three families are pairwise disjoint by construction ( Review
Reasonableness: Density check: we picked $3$ out of every $10$ integers, so $|S| \approx \tfrac{3}{10} \cdot 2024 = 607.2$. Our exact count $608$ sits right at that ceiling — perfect. Compare with naive bounds: ignoring the odd rule, gap-$\ge 3$ alone allows about $2024/3 \approx 674$ elements (choices A/D/E live in that range), and the odd rule must shave that down. It shaves it from roughly $675$ down to $608$ — a sensible "one odd kicked out per block of $10$" loss. So $608$ is consistent both with the construction and with answer choice (C).
Alternative: Tool #3 (Eliminate Possibilities): the upper bound $|S| \le \lfloor 2024/3 \rfloor + 1 = 675$ rules out nothing new, but the odd-rule lower-density argument — at most one odd per block of $8$ consecutive integers, so at most $\lceil 2024/8 \rceil = 253$ odds, and the remaining even members satisfy gap $\ge 3$ around each odd, giving roughly $3$ per length-$10$ window — quickly squeezes the answer into the $600$s. Among the choices, only (C) $608$ matches the $\tfrac{3}{10}$ density that the greedy construction achieves.
CCSS standards used (min grade 6)
6.EE.B.8Write an inequality of the form $x > c$ or $x < c$ to represent a constraint, and recognize its solution set (Translating the two strict-gap rules into the working forms $|x - y| \ge 3$ and (for odds) $|x - y| \ge 8$, and counting non-negative integers $k$ with $A + 10k \le 2024$ for each of the three families.)5.OA.B.3Generate two numerical patterns using two given rules; form ordered pairs and identify relationships (Building the greedy set $1, 4, 8, 11, 14, 18, \dots$ term-by-term and recognizing the repeating gap block $(+3, +4, +3)$ of total length $10$.)6.EE.A.2Write, read, and evaluate expressions in which letters stand for numbers (Naming the three arithmetic progressions inside $S$ as $1 + 10k$, $4 + 10k$, $8 + 10k$ with a single index $k$, which converts the counting problem into solving three linear inequalities.)
⭐ On a packing problem, build greedily on a small slice and watch for a repeating gap block — here the block is "3 numbers every 10 integers," and the answer is just $\tfrac{3}{10}$ of $2024$, rounded by the family counts.
⭐ On a packing problem, build greedily on a small slice and watch for a repeating gap block — here the block is "3 numbers every 10 integers," and the answer is just $\tfrac{3}{10}$ of $2024$, rounded by the family counts.
More like this
Same archetype — closest grade level first.
