Question

Let S be a subset of {1, 2, 3,... 100}, containing 50 elements. How many such sets have the property that every two numbers in S have a common divisor that is greater than 1?

I really need help. Give me a good explanation with he answer. Thanks!!! :)

Answer 1

Let S2 be the subset containing all the multiples of 2. There are 50 of them, and they all have 2 as a divisor. So, S2 is one of our subsets.

There are fewer than 50 multiples of any other number in a subset of {1 ... 100}.

Looks like S2 is our only candidate.