150k views
0 votes
a subset of the integers 1, 2, . . . , 100 has the property that none of its members is 5 times another. what is the largest number of members such a subset can have? (a) 72 (b) 77 (c) 84 (d) 85 (e) 86

User Subs
by
7.6k points

1 Answer

7 votes

Answer:

Let's assume that the subset contains as many numbers as possible. We start by including all the numbers from 1 to 100 that are not divisible by 5. These are the numbers 1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 21, 22, 23, 24, 26, 27, 28, 29, 31, 32, 33, 34, 36, 37, 38, 39, 41, 42, 43, 44, 46, 47, 48, 49, 51, 52, 53, 54, 56, 57, 58, 59, 61, 62, 63, 64, 66, 67, 68, 69, 71, 72, 73, 74, 76, 77, 78, 79, 81, 82, 83, 84, 86, 87, 88, 89, 91, 92, 93, 94, 96, 97, 98, 99.

This gives us a subset of 81 numbers. However, we need to remove any numbers that are multiples of other numbers in the subset. For example, if we include the number 6, we must remove 12, 18, 24, etc. Similarly, if we include the number 9, we must remove 18, 27, 36, etc. We can see that the only numbers that have multiples in the subset are 2, 3, 7, 8, 13, 17, 18, 19, 27, 28, 37, 38, 39, 52, 53, 54, 57, 58, 59, 68, 69, 73, 74, 78, 79, 83, 84, 87, 88, 89, 92, 93, 94, and 98.

Therefore, we need to remove these 34 numbers from the subset. This leaves us with a subset of 81 - 34 = 47 numbers.

However, we can still include the number 5, since it is not a multiple of any other number in the subset. This adds one more number to the subset, giving us a total of 48 numbers.

Therefore, the largest number of members that such a subset can have is 48, which corresponds to answer choice (e).

User Oren Matar
by
7.2k points