Question

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

• If $x$ and $y$ are distinct elements of $S,$ then $|x - y| \gt 2.$

• If $x$ and $y$ are distinct odd elements of $S,$ then $|x - y| \gt 6.$

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

$436$

$506$

$608$

$654$

$675$

Solution:

The two conditions say chosen numbers are at least $3$ apart, and chosen odd numbers at least $7$ apart. Try the pattern $1, 4, 8, 11, 14, 18, \ldots$ (residues $1, 4, 8 \pmod{10}$ ). Every gap is $\ge 3,$ and each block of $10$ holds exactly one odd number, so the odds stay $10$ apart. That's $3$ numbers per $10.$ Now $\{1, \ldots, 2024\}$ is $202$ full blocks plus $2021, 2024,$ so the count is $202 \cdot 3 + 2 = 608.$ Each block of $10$ can hold at most $3$ elements, so we can't do better. Therefore, the answer is C.

2024 AMC 10A Problem 20

Solution:

Problem 20 in Other Years