Maths Olympiad Prep

Library / /19 of 520

Combinatorics Difficulty 6.2 National olympiad Find the answer

A subset of the integers 1,2,...,1001, 2, ..., 100 has the property that none of its members is 3 times another. What is the largest number of members such a subset can have?

Pick one

Solution

To solve this problem, we need to find the largest subset of the integers from 1 to 100 such that no member of the subset is three times another member. We will use a systematic approach to count the elements that can be included in the subset.

1. Identify the multiples of 3:
- The multiples of 3 within the range 1 to 100 are: 3,6,9,12,,993, 6, 9, 12, \ldots, 99.
- There are 1003=33\left\lfloor \frac{100}{3} \right\rfloor = 33 multiples of 3.

2. Remove the multiples of 3:
- Removing these 33 multiples from the set of 100 integers leaves us with 10033=67100 - 33 = 67 elements.

3. Add back the multiples of 9:
- The multiples of 9 within the range 1 to 100 are: 9,18,27,,999, 18, 27, \ldots, 99.
- There are 1009=11\left\lfloor \frac{100}{9} \right\rfloor = 11 multiples of 9.
- Adding these 11 elements back to the 67 elements gives us 67+11=7867 + 11 = 78 elements.

4. Remove the multiples of 27:
- The multiples of 27 within the range 1 to 100 are: 27,54,8127, 54, 81.
- There are 10027=3\left\lfloor \frac{100}{27} \right\rfloor = 3 multiples of 27.
- Removing these 3 elements from the 78 elements gives us 783=7578 - 3 = 75 elements.

5. Add back the multiples of 81:
- The multiples of 81 within the range 1 to 100 are: 8181.
- There is 10081=1\left\lfloor \frac{100}{81} \right\rfloor = 1 multiple of 81.
- Adding this 1 element back to the 75 elements gives us 75+1=7675 + 1 = 76 elements.

Thus, the largest subset of the integers from 1 to 100 such that no member is three times another member contains 76 elements.

The final answer is 76\boxed{76}.

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.