ISI 2004 MIII

Question

A subset $S$ of set of numbers $\{2,3,4,5,6,7,8,9,10\}$ is said to be good if has exactly $4$ elements and their $gcd=1$, Then number of good subset is

• A. $126$
• B. $125$
• C. $123$
• D. $121$

Comments

We have to subtract all the cases where gcd of all numbers is 1 

This should be: We have to substract all those cases where GCD of all nos. in NOT 1 .

Also GCD becomes 2 only when all four nos. in the subset are even.

Even A single prime can make the subset good.

Isn't it? @ Mandeep Singh

Answer 1

$S = \{2,3,4,5,6,7,8,9,10\} , |S| = 9$

Total no of subsets with cardinality $4 = C(9 , 4 ) = 126$

The subsets with cardinality $4$ which having $gcd \neq 1$ is possible only when subset contains only even numbers.

Here even no $E = \{2,4,6,8,10\}$ 

No. of subsets with cardinality $4$ from set $E = C(5 , 4) = 5$.

1. $\{2,4,6,8\}$
2. $\{2,4,6,10\}$
3. $\{2,4,8,10\}$
4. $\{2,6,8,10\}$
5. $\{4,6,8,10\}$

So,there are $5$ subsets which having $gcd = 2$  i.e  $gcd \neq 1$ 

So, Total no subsets with cardinality $4$ which having $gcd = 1$  is $126 - 5 =121$

The correct answer is (D)121

Comments

nice explanation....

---

this was the best approach

I think one way to solve these questions if stuck is to start solving them other way around like this solution

Total - not possible ones

Answer 2

Selecting $4$ numbers from $9$ is $^9C_4 = 126.$
We have to subtract all the cases where gcd of all numbers is $1$ and this can only happen when all number should not be even. Which is $^5C_4=5$
So answer will be $126-5=121.$

Comments

We have to subtract all the cases where gcd of all numbers is 1 and this can only happen when all number should not be even.

GCD of all number can be one in another case also

when three of them are odd and one is even

---

Yes i am taking only the case where all 4 are even. If a single element is odd then gcd will be 1 and subset is good. Since total 5 elements are even, 5 bad subsets are there.

---

we have to find subsets with gcd =1,so why are u subtracting 5 from 126 as u r saying 5 subsets have gcd =1

---

These 5 don't have gcd 1. In fact they have gcd 2 because of even numbers all.

Answer 3

Total number of sub sets which will contain exactly 4 elements = 9C4= 126

Now eliminate all the sets of 4 elements which can cause GCD other than 1 ,here by observing only GCD of 2 can exist other than 1 with 4 elements and those 4 elements can be from {2,4,6,8,10}.

Thus with these 5 elements  5c4 = 5 sub sets are possible which have gcd other than 1.

So, good subsets = 126 - 5 = 121...

Answer 4

Please tell what is wrong with this solution ...I am getting 6 !!!!!

 Numbers are 2,3,2^2,5,2*3,7,2^3,3^2,2*5

There are 4 prime numbers involved which are 2,3,5,7.

Since a good subset should have exactly 4 elements which are co-prime, those numbers must choose 1 of these primes as factors without repetition

That means we cannot have 2*3, and 2*5 in the good subset because it will force us to choose a factor twice.

Now , in the remaining numbers,

2 can be chosen from 2,2^2,2^3 ----- (3 ways)

3 can be chosen from 3,3^2------------(2 ways)

5 can be chosen from 5-------------------(1 way)

7 can be chosen from 7-------------------(1 way)

 So total number of "good" subsets = 3*2*1*1=6

Comments

you said good set cannot have 6,10 but we can

{2,4,6,7} and {2,4,7,10} both set GCD is 1

---

yes, you are forcing all elements to be co-prime whereas just one prime is enough to ensure GCD is 1.

---

ohh yeah ryt !! i got it....thanks :)

So As i understand it, except 2 (which appears in 5 numbers) all others appear in less than 4 numbers only, So only '2' can contribute to a non-good subset.....therefore as in the prev ans, we subtract the case where all numbers are multiples of 2.....to obtain number of good subsets ....ryt?