2024 AMC 10A Problem 20

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

Any two chosen numbers differ by at least

3,

and any two chosen odd numbers differ by at least

7

A repeating block of

10

can hold at most

3

chosen numbers with only one odd; try residues

1, 4, 8

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.

Problem 20 in other years