# Math Really Hard

Let S be a subset of {1, 2, 3,...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?

1. 👍 0
2. 👎 0
3. 👁 797
1. this is wrong

1. 👍 0
2. 👎 0
2. I would suggest using the aops website.

1. 👍 0
2. 👎 0
3. We claim that there is only one such set, namely \$\{2, 4, 6, \dots, 98, 100\}\$.

The solution hinges on the following observation: The greatest common divisor of two consecutive numbers (like 20 and 21) is 1. We can see this as follows: If \$d\$ divides both \$n\$ and \$n + 1\$, then \$d\$ must divide their difference, which is \$(n + 1) - n = 1\$. But then, the only possible value of \$d\$ is 1.

Therefore, no two elements in \$S\$ can be consecutive. Also, we note that \$S\$ cannot contain the element \$1\$, since the greatest common divisor of \$1\$ with any integer is \$1\$. Therefore, \$S\$ is a subset of \$\{2, 3, 4, \dots, 100\}\$ with 50 elements and no two elements consecutive. The only such set is \$\{2, 4, 6, \dots, 98, 100\}\$.

The set {2, 4, 6,.....98, 100\} has the desired property, because every element is even, so any two numbers in S have 2 as a common divisor.

Therefore, the number of sets \$S\$ that have the given property is \$\boxed{1}\$.
Hint(s):

1. 👍 0
2. 👎 0
4. 1

1. 👍 0
2. 👎 0

## Similar Questions

1. ### Sets

Suppose Set B contains 69 elements and the total number elements in either Set A or Set B is 107. If the Sets A and B have 13 elements in common, how many elements are contained in set A?

2. ### Math

How many different functions are there from a set with 10 elements to sets with the following numbers of elements? a) 2 b) 3 c) 4 d) 5

3. ### Math

Consider the set of integers greater than -2 and less than 6. A subset of this set is the positive factors of 5. What is the complement of this subset? a. {0,2,3,4} b. {-1,0,2,3,4} c. {-2,-1,0,2,3,4,6} d. {-2,-1,0,1,2,3,4,5,6} I

4. ### elmentary math for educators

Suppose B is proper subset of C. If n(c)=8, what is the maximum number of elements n B? What is the least possible number of elements B?

1. ### MATH

List the elements of the following sets where P = {1,2,3...} A={x:x € P, 3 < x < 12} B={x:x € P, x is even, x < 15} C={x:x € P, 4 + x € 3} D={x:x € P, x is multiple of 5}

2. ### Public Finance

Suppose the marginal social cost of television sets is \$100. This is constant and equal to the average cost of television sets. The annual demand for television sets is given by the following equation: Q = 200,000 – 500P2. If

3. ### Math

How many different functions are there from a set with 10 elements to sets with the following numbers of elements? a) 2 b) 3 c) 4 d) 5

4. ### logic and set theory

describe the venn diagram for two disjoint sets. how does this diagram illustrate that the sets have no common elements? ... im a bit confused, because to me, if the sets are disjoint and hence nothing is in common, it wouldnt be

1. ### Math

In an experiment, a pair of dice is rolled and the total number of points observed. (a) List the elements of the sample space (b) If A = { 2, 3, 4, 7, 8, 9, 10} and B = {4, 5, 6, 7, 8} list the outcomes which comprise each of the

2. ### Discrete Math

For sets A, B, C is a subset of U, prove or disprove (with a counter-example) the following: If A is a subset of B, B is not a subset of C, then A is not a subset of C,

3. ### math

2-2A #2 Rewrite the following using mathematical symbols: a. P is equal to the set containing a, b, c, and d. b. The set consisting of the elements 1 and 2 is a proper subset of {1, 2, 3, 4} c. The set consisting of the elements 0