Maths Olympiad Prep

Library / /123 of 520

Combinatorics Difficulty 6.5 National olympiad Find the answer

Let S=1,2,,100.S = {1, 2, \cdots, 100}. XX is a subset of SS such that no two distinct elements in XX multiply to an element in X.X. Find the maximum number of elements of XX.

2022 CCA Math Bonanza Individual Round #3

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

Solution

To solve this problem, we need to find the maximum number of elements in a subset X X of S={1,2,,100} S = \{1, 2, \ldots, 100\} such that no two distinct elements in X X multiply to an element in X X .

1. Understanding the Problem:
- We need to ensure that for any a,bX a, b \in X (where ab a \neq b ), the product abX ab \notin X .

2. Constructing a Candidate Set:
- Consider the set X={10,11,12,,100} X = \{10, 11, 12, \ldots, 100\} . This set contains 91 elements.

3. Verifying the Condition:
- We need to check if for any a,bX a, b \in X (where ab a \neq b ), the product abX ab \notin X .
- For a,b{10,11,12,,100} a, b \in \{10, 11, 12, \ldots, 100\} , the smallest possible product is 10×11=110 10 \times 11 = 110 , which is greater than 100.
- Therefore, no product of two distinct elements in X X will be in X X .

4. Optimality:
- To determine if this is the maximum possible size, consider the following:
- If we include any number less than 10 in X X , say k k , then k×10100 k \times 10 \leq 100 , which would force k×10 k \times 10 to be in X X , violating the condition.
- Thus, including any number less than 10 would reduce the size of X X while maintaining the condition.

5. Conclusion:
- The set X={10,11,12,,100} X = \{10, 11, 12, \ldots, 100\} is optimal because it maximizes the number of elements while satisfying the given condition.

The final answer is 91 \boxed{91} .

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