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}
<span>Answer: only 1: the set {2, 4, 6, …100}</span>
