Maths Olympiad Prep

Library / /1 of 4

Combinatorics Difficulty 6.0 National olympiad Find the answer

Does the set {1,2,3,...,3000}\{1,2,3,...,3000\} contain a subset A A consisting of 2000 numbers that xAx\in A implies 2xA2x \notin A ?!! :?:

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let's consider the set S={1,2,3,,3000} S = \{1, 2, 3, \ldots, 3000\} . We are tasked with determining whether there exists a subset AS A \subseteq S such that A=2000 |A| = 2000 and for every element xA x \in A , the element 2xA 2x \notin A .

To solve this problem, we first think about the constraints imposed by the requirement xA    2xA x \in A \implies 2x \notin A . This means that for each x x included in the subset A A , its double 2x 2x cannot also be in A A .

1. Counting the Valid Elements:
- A number x x in set S S can have its double 2x 2x in the same set provided 2x3000 2x \leq 3000 .
- The largest integer x x for which 2x3000 2x \leq 3000 is x=1500 x = 1500 .

2. Construction of Subset:
- We can construct A A such that A A contains as many numbers as possible, none of which have their doubles also included.
- We start by considering the largest possible numbers in S S which do not have their doubles in S S . These are 1501,1502,,3000 1501, 1502, \ldots, 3000 .

3. Counting the Available Space:
- The subset {1501,1502,,3000} \{1501, 1502, \ldots, 3000\} consists of 30001500=1500 3000 - 1500 = 1500 elements.
- This subset satisfies the condition because the smallest element 1501 1501 when doubled is greater than 3000, hence not in S S .

4. **Attempt to Extend A A :**
- We need at least 2000 elements in A A . The previous subset only has 1500 elements.
- To achieve 2000 elements, any additional elements must come from the set {1,2,,1500}\{1, 2, \ldots, 1500\} without violating the condition 2xA 2x \notin A .

5. Limitations:
- Selecting any value from {1,2,,1500}\{1, 2, \ldots, 1500\} means its double 2x 2x also has the potential to be in {1,2,,3000}\{1, 2, \ldots, 3000\}, specifically in {2,4,,3000}\{2, 4, \ldots, 3000\}.
- This constraint makes it impossible to construct a valid set A A of size 2000, as any expansion beyond the initial 1500 would immediately conflict with the condition.

Hence, the answer to the question is:

No \boxed{\text{No}}
This solution demonstrates that it is not possible to construct a subset AS A \subseteq S that contains 2000 elements while satisfying the condition that no element has its double also in the subset.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.