2024 AMC 10A Problem 20

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?

Show solution

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.

Tagged: arrangements with restrictions · extremal argument · optimization