Question

Let $s$ be a subset of $\{1, 2, 3, \dots, 100\}$, containing $50$ elements. how many such sets have the property that every pair of numbers in $s$ has a common divisor that is greater than 1?

Answer 1

Let A be the set {1, 2, 3, 4, 5, ...., 99, 100}.

The set of Odd numbers O = {1, 3, 5, 7, ...97, 99}, among these the odd primes are :

P={3, 5, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}

we can count that n(O)=50 and n(P)=24.

 

 

Any prime number has a common factor >1 with only multiples of itself.

For example 41 has a common multiple >1 with 41*2=82, 41*3=123, which is out of the list and so on...

For example consider the prime 13, it has common multiples >1 with 26, 39, 52, 65, 78, 91, and 104... which is out of the list.

Similarly, for the smallest odd prime, 3, we see that we are soon out of the list:

3, 3*2=6, 3*3=9, ......3*33=99, 3*34=102.. 

we cannot include any non-multiple of 3 in a list containing 3. We cannot include for example 5, as the greatest common factor of 3 and 5 is 1.

This means that none of the odd numbers can be contained in the described subsets.

 

 

Now consider the remaining 26 odd numbers:

{1, 9, 15, 21, 25, 27, 33, 35, 39, 45, 49, 51, 55, 57, 63, 65, 69, 75, 77, 81, 85, 87, 91, 93, 95, 99}

which can be written in terms of their prime factors as:

{1, 3*3, 3*5, 3*7, 5*5,3*3*3, 3*11,5*7, 3*13, 2*2*3*3, 7*7, 3*17, 5*11 , 3*19,3*21, 5*13, 3*23,3*5*5, 7*11, 3*3*3*3, 5*17, 3*29, 7*13, 3*31, 5*19, 3*3*11}

 

1 certainly cannot be in the sets, as its common factor with any of the other numbers is 1.

3*3 has 3 as its least factor (except 1), so numbers with common factors greater than 1, must be multiples of 3. We already tried and found out that there cannot be produced enough such numbers within the set { 1, 2, 3, ...}

 

3*5: numbers with common factors >1, with 3*5 must be 

either multiples of 3: 3, 3*2, 3*3, ...3*33 (32 of them)

either multiples of 5: 5, 5*2, ...5*20 (19 of them)

or of both : 15, 15*2, 15*3, 15*4, 15*5, 15*6 (6 of them)

 

we may ask "why not add the multiples of 3 and of 5", we have 32+19=51, which seems to work.

The reason is that some of these 32 and 19 are common, so we do not have 51, and more important, some of these numbers do not have a common factor >1:

for example: 3*33 and 5*20

so the largest number we can get is to count the multiples of the smallest factor, which is 3 in our case.

 

By this reasoning, it is clear that we cannot construct a set of 50 elements from {1, 2, 3, ....}  containing any of the above odd numbers, such that the common factor of any 2 elements of this set is >1.

 

What is left, is the very first (and only) obvious set: {2, 4, 6, 8, ...., 48, 50}

 

Answer: only 1: the set {2, 4, 6, …100}