1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
oksian1 [2.3K]
3 years ago
13

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?
Mathematics
1 answer:
Tamiku [17]3 years ago
8 0

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>

You might be interested in
If one coin is flipped and then a second coin is flipped, what is the probability that both coins turn up tails? question 18 opt
Mademuasel [1]
First you find the probability of each coin turning up tails, then you multiply the two probabilities together:
1/2 x 1/2 = 1/4
4 0
3 years ago
Kevin is riding his bike on a 10 1/8 mile bike path. He has covered 5 3/4 miles already. How many miles does he have left to cov
zhuklara [117]
So he has road 5.75 miles and 1/8=0.125 so i am going to estimate but 4.12 miles left to cover 
7 0
3 years ago
Write the equation of the line in Point-Slope Form with a slope of 2/3 and
baherus [9]

Answer:

y=2/3+4

Step-by-step explanation:

the formula is y=mx+b. b is 4 and m is your slope.

3 0
3 years ago
Read 2 more answers
Please help ASAP!<br> Questions 1-4
marusya05 [52]

Answer:

it is a test I am not going to help

Step-by-step explanation:

6 0
3 years ago
Read 2 more answers
. Suha has a full 600 ml bottle of wallpaper remover. She is going to mix some of the wallpaper remover with water. Here is the
erik [133]

Answer:

100 ml

Step-by-step explanation:

5 0
2 years ago
Read 2 more answers
Other questions:
  • What’s the value and what makes the x in the equation -6(x+11)+ 2x = 70 true ?
    6·2 answers
  • Suppose tortilla Chips cost 25.5 cents per ounce. What would a bag of chips cost if it contained 23oz?
    15·1 answer
  • Find the volume and total surface area of a cone with a radius of 3 and a height of 5.
    15·1 answer
  • What operations do I use
    12·1 answer
  • Which inequality is represented by the graph?
    11·1 answer
  • What is -23-x-x+16-2
    10·2 answers
  • Dalin is 16 years old hey sister is 3/4 of his age How old is his sister
    10·1 answer
  • Does the graph represent an arithmetic sequence or geometric sequence?
    10·1 answer
  • I need help with my Algebra 1 ugh plz help! Sorry there’s a typo
    13·1 answer
  • Helppppppppppppppppppp
    8·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!