AMC 10 · 2024 · #20

Grade 6 countingnumber-theory

Archetype Lattice / Grid Pattern from Small Cases └ Sub-archetype Periodic Placement Formula

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

📏 Medium solution 💡 3 insights

Problem

Pick as many numbers as possible from {1, 2, 3, …, 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?

Pick an answer.

(A)

436

(B)

506

(C)

608

(D)

654

(E)

675

AMC 10 2024 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

How to solve

Strategy Solve an Easier Related Problem

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, … Tool #5 (Look for a Pattern) takes over — the consecutive gaps cycle +3, +4, +3, +3, +4, +3, …, 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).

1STEP 1

Restate the rules: any two picks differ by ≥ 3, any two odds by ≥ 8 (two odds differ by an even number, so "more than 6" means ≥ 8).

|x - y| ≥ 3 for any two in S; |x - y| ≥ 8 for any two odds in S

2STEP 2

Greedy from 1, always the smallest legal next integer — 7 fails (|7-1|=6 breaks the odd rule), so the build is 1, 4, 8, 11, 14, 18, 21, ….

S ⊇ {1, 4, 8, 11, 14, 18, 21, 24, 28, 31, …}

3STEP 3

Consecutive gaps cycle +3, +4, +3 — a block of length 10 — so 3 numbers land in every 10 integers, repeating as a_n+3 = a_n + 10.

(gaps) = (+3, +4, +3)= 10, (+3, +4, +3)= 10, …

4STEP 4

The triple (1, 4, 8) plus the +10 shift splits S into three progressions: 1+10k, 4+10k, 8+10k (k ≥ 0); only 1+10k is odd.

S = {1 + 10k} ∪ {4 + 10k} ∪ {8 + 10k}, k = 0, 1, 2, …

5STEP 5

Solve A + 10k ≤ 2024 per family: 1+10k → k ≤ 202.3, 4+10k → k ≤ 202, 8+10k → k ≤ 201.6, giving family counts 203, 203, 202.

|I| = 203, |II| = 203, |III| = 202

6STEP 6

Add the disjoint family counts (residues 1, 4, 8 mod 10): 203 + 203 + 202 = 608 → (C); the greedy build proves no denser legal set exists.

|S| = 203 + 203 + 202 = 608 → (C)

Answer

608

Density check: we picked 3 out of every 10 integers, so |S| ≈

\frac{3}{10}

· 2024 = 607.2. Our exact count 608 sits right at that ceiling — perfect. Compare with naive bounds: ignoring the odd rule, gap- ≥ 3 alone allows about

\frac{2024}{3}

≈ 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).

💡Key takeaway

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 $\frac{3}{10}$ of 2024, rounded by the family counts.

More like this