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?
4 answers
this is wrong
I would suggest using the aops website.
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):
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):
If you cant read that ^ the answer is 1
1 answer