AMC 10 A

Combinatorics Difficulty 5.1 AIME, harder Find the answer United States

Let $S$ be a subset of $\{1, 2, 3, \dots, 2024\}$ such that the following two conditions hold:
* If $x$ and $y$ are distinct elements of $S$ , then $|x - y| > 2$ .
* If $x$ and $y$ are distinct odd elements of $S$ , then $|x - y| > 6$ .
What is the maximum possible number of elements in $S$ ?

Pick one

Solution

Answer (C): If $S$ consists of the positive integers less than or equal to $2024$ that are congruent to $1$ , $4$ , or $8$ modulo $10$ , then every pair of elements in $S$ differ by at least $|4 - 1| = |11 - 8| = 3$ , and every pair of odd elements of $S$ differ by at least $|11 - 1| = 10$ . This set,
$\{1, 4, 8, 11, 14, 18, \dots, 2011, 2014, 2018, 2021, 2024\},$
satisfies the given conditions and has $3 \cdot (\frac{2020}{10}) + 2 = 608$ elements. To see that no larger set satisfies the given conditions, note that if a set satisfies the first condition and some block of $10$ consecutive integers contains $4$ elements of the set, then those $4$ elements would need to be the $1$ st, $4$ th, $7$ th, and $10$ th elements in that block, and the two odd numbers among them would differ by $6$ , in violation of the second condition. Therefore there are at most $3 \cdot 202 = 606$ elements of $S$ among the first $2020$ positive integers, and at most $2$ elements of $S$ can be among $\{2021, 2022, 2023, 2024\}$ .

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.