AMC 10 · 2024 · #20

Grade 6 countingnumber-theory

Archetype Lattice / Grid Pattern from Small Cases

pattern-recognitionsequences-arithmeticsystematic-enumerationparity easier-related-problempattern-recognitionoptimization-counting ↑ Prerequisites: sequences-arithmeticmultiplesparity

📏 Medium solution 💡 3 insights

Problem

Let $S$ be a subset of $\{1, 2, 3, \dots, 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$ ?

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

Pick an answer.

(A)

436

(B)

506

(C)

608

(D)

654

(E)

675

View mode:

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

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

#9 Solve an Easier Related Problem 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.

$$|x - y| \ge 3 \text{ for any two in } S; \quad |x - y| \ge 8 \text{ for any two odds in } S$$

💡 Translating "$|x-y| > 2$" into "$|x-y| \ge 3$" is Grade 6 inequality reading: strict inequality on integers means the next integer up.

#9 Solve an Easier Related Problem 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$

$$S \supseteq \{1,\, 4,\, 8,\, 11,\, 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 Look for a Pattern 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$.

$$(\text{gaps}) = \underbrace{(+3, +4, +3)}_{=\,10}, \underbrace{(+3, +4, +3)}_{=\,10}, \dots$$

💡 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.

#5 Look for a Pattern 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$.

$$S = \{1 + 10k\} \cup \{4 + 10k\} \cup \{8 + 10k\}, \quad k = 0, 1, 2, \dots$$

💡 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.

#9 Solve an Easier Related Problem 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.

$$|\text{I}| = 203, \quad |\text{II}| = 203, \quad |\text{III}| = 202$$

💡 Each family count is the same Grade 6 inequality-counting drill: how many non-negative integers $k$ satisfy $A + 10k \le 2024$?

#9 Solve an Easier Related Problem 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.

$$|S| = 203 + 203 + 202 = 608 \;\Rightarrow\; \textbf{(C)}$$

💡 Disjoint-by-residue counts add cleanly — exactly the Grade 5 "count by groups, then add" structure.

[1] #9 6.EE.B.8 Restate the two gap rules in usable form. Rule 1 says any two chosen integers di

[2] #9 5.OA.B.3 Greedy-construct the densest legal set starting from $1$. At each step pick the

[3] #5 5.OA.B.3 Read the pattern out of the gap sequence. The consecutive differences are $3, 4,

[4] #5 6.EE.A.2 Split $S$ into three arithmetic progressions. The starting triple $(1, 4, 8)$ pl

[5] #9 6.EE.B.8 Count the legal $k$ in each family by solving an inequality. Family I needs $1 +

[6] #9 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.8 Write 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.3 Generate 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.2 Write, 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.

Problem

Toolkit + CCSS Solution

Understand

Plan

Execute — Answer: C

Review

CCSS standards used (min grade 6)

More like this