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

Respond to this Question

First Name

Your Response

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

  4. Business Math

    Being inventory of 12 sets of paints at a cost of $1.50 each. During the year the store purchased 4 sets at $1.60, 6 sets at $2.20, 6 sets at $2.50, and 10 sets at $3.00. By the end of the year, 25 sets were sold. Caculate the

You can view more similar questions or ask a new question.