2024 AMC 10A Problem 20

Start small to see what goes wrong. The simplest idea is to take every third number: $1, 4, 7, 10, 13, \ldots$. But $1$ and $7$ are both odd and only $6$ apart, which breaks the second rule. So we cannot pack members every $3$ steps for long. The question is how often we can.

This is a "maximum" question, so it has two halves.

Part 1: no stretch of $10$ numbers in a row holds more than $3$ members.

1. Take any $10$ numbers in a row, from $k$ to $k + 9$. Members must be at least $3$ apart.
2. Could $4$ members fit? The first and the last would be at least $3 + 3 + 3 = 9$ apart, and the stretch is only $9$ long. So the only way is exactly $k, k + 3, k + 6, k + 9$.
3. But $k$ and $k + 6$ are both odd or both even, and so are $k + 3$ and $k + 9$. One of $k$ and $k + 3$ is odd. So one of these pairs is two odd members only $6$ apart. Not allowed.
4. So each block of $10$ numbers in a row holds at most $3$ members.
5. Cut $1$ to $2024$ into $202$ blocks of ten ($1$ to $10$, $11$ to $20$, and so on up to $2011$ to $2020$) plus the leftover $2021, 2022, 2023, 2024$. The leftover four numbers can hold at most $2$ members (they must be $3$ apart). So there are at most $202 \cdot 3 + 2 = 608$ members.

Part 2: $608$ members is possible.

1. In each block of ten, take the numbers ending in $1$, $4$ and $8$: that is $1, 4, 8, 11, 14, 18, 21, \ldots, 2011, 2014, 2018$. Then add $2021$ and $2024$.
2. Check rule 1: the gaps go $3, 4, 3, 3, 4, 3, \ldots$ and at the end $2018 \to 2021 \to 2024$ are gaps of $3$. Every gap is more than $2$.
3. Check rule 2: the only odd members are the ones ending in $1$: $1, 11, 21, \ldots, 2021$. They are $10$ apart, which is more than $6$.
4. Count: $202$ blocks with $3$ each, plus $2$, is $608$.

At most $608$ and exactly $608$ is possible, so the maximum is $608$.

The answer is $\boxed{\textbf{(C)}\ 608}$.

For "spread out as many as possible" problems, find a short stretch and ask how many members fit in it; that gives a limit you can repeat across the whole range. Try a few lengths until the rules really start to bite, which here happens at $10$. Then show a repeating pattern that meets the limit, and handle the leftover numbers at the end separately.

Upper bound. Take any $10$ consecutive integers. Elements of $S$ are pairwise at least $3$ apart, so at most $4$ of them lie in this stretch, and $4$ is possible only if they are $k, k+3, k+6, k+9$. But then $k, k+6$ share a parity and so do $k+3, k+9$; one of these pairs consists of two odd elements only $6$ apart, contradicting the second condition. So every $10$ consecutive integers contain at most $3$ elements of $S$.

Cut $\{1, \dots, 2024\}$ into $202$ blocks of ten ($1$–$10$, …, $2011$–$2020$) plus the leftover $\{2021, 2022, 2023, 2024\}$, which holds at most $2$ elements (they must be $3$ apart). Hence $|S| \le 202\cdot 3 + 2 = 608$.

Construction. In each block take $10k+1,\ 10k+4,\ 10k+8$ for $k = 0, 1, \dots, 201$, and add $2021$ and $2024$. Consecutive elements differ by $3, 4, 3, 3, 4, 3, \dots$ and finally $2018 \to 2021 \to 2024$ by $3$, so all gaps exceed $2$. The odd elements are exactly $1, 11, 21, \dots, 2021$, spaced $10$ apart, which exceeds $6$. This $S$ has $608$ elements.

The answer is $\boxed{\textbf{(C)}\ 608}$.