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$

Answer: C

Concepts:arrangements with restrictions extremal argument optimization

Difficulty rating: 2080

Solution:

The two conditions say chosen numbers are at least $3$ apart, and chosen odd numbers at least $7$ apart. Any four numbers in a block of $10$ would need three gaps of at least $3,$ so they would have to occupy positions $r,r+3,r+6,r+9.$ Two of the odd entries would then differ by $6,$ which is forbidden. Thus each full block of $10$ contains at most $3$ choices, and the last four positions contain at most $2.$ This gives the upper bound $202\cdot3+2=608.$ It is attained by the pattern $1,4,8,11,14,18,\ldots$ (residues $1,4,8\pmod{10}$ ), together with $2021,2024.$ Adjacent selected values differ by at least $3,$ and the selected odd values are $10$ apart. Therefore, the answer is C.

2024 AMC 10A Problem 20

Answer: C

Difficulty rating: 2080

Solution:

Problem 20 in Other Years