Maths Olympiad Prep

Library / /21 of 26

Combinatorics Difficulty 5.1 AIME, harder Find the answer United States

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

Pick one

Solution

Answer (C): If SS consists of the positive integers less than or equal to 20242024 that are congruent to 11, 44, or 88 modulo 1010, then every pair of elements in SS differ by at least 41=118=3|4 - 1| = |11 - 8| = 3, and every pair of odd elements of SS differ by at least 111=10|11 - 1| = 10. This set,
{1,4,8,11,14,18,,2011,2014,2018,2021,2024}, \{1, 4, 8, 11, 14, 18, \dots, 2011, 2014, 2018, 2021, 2024\},
satisfies the given conditions and has 3(202010)+2=6083 \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 1010 consecutive integers contains 44 elements of the set, then those 44 elements would need to be the 11st, 44th, 77th, and 1010th elements in that block, and the two odd numbers among them would differ by 66, in violation of the second condition. Therefore there are at most 3202=6063 \cdot 202 = 606 elements of SS among the first 20202020 positive integers, and at most 22 elements of SS can be among {2021,2022,2023,2024}\{2021, 2022, 2023, 2024\}.

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

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