GATE CSE 2006 | Question: 25

Question

Let $S = \{1, 2, 3,\ldots, m\}, m >3.$ Let $X_1,\ldots,X_n$ be subsets of $S$ each of size $3.$ Define a function $f$ from $S$ to the set of natural numbers as, $f(i)$ is the number of sets $X_j$ that contain the element $i.$ That is $f(i)=\left | \left\{j \mid i\in X_j \right\} \right|$   then $ \sum_{i=1}^{m} f(i)$ is:

• A. $3m$
• B. $3n$
• C. $2m+1$
• D. $2n+1$

Comments

@mehul vaidya

First of all it is clearly given in the question that $\mathbf{m>3}$, therefore the example which you took turns out to be $\textbf{False}$

---

It has been explained but still one more explanation will not hurt.

What is this $\binom{m}{3} and \binom{m-1}{3}$, what they are trying to do ?

Say we have 5 elements in our set(this is m=5), now how many subsets can be formed of size 3, it simple combination formula $\binom{m}{3}$=$\binom{5}{3}$,

$\binom{5}{3}$ =$\frac{5!}{3!*2!}$=10 ………….….(this is n)

we want to find out how many of these sets will have element 1 in them.

Which also means that we want sets which are totally made up of elements which are not 1.

we can model this by taking {2,3,4,5} excluding 1 and this is that $\binom{m-1}{c}$ thing we saw earlier.

$\binom{4}{c}=\frac{4!}{3!}$=4

which means that out of all those 10 sets 4 will not contain 1 in them and remaining 6 will contain 1 in them.

---

..................….......….

Answer 1

$|S|=m$

No. of three elements subset $=n=\binom{m}{3}$

Function $f(i)$ is defined as No. of three elements subset which contain element $i$.

Without loss of generality, lets assume $i=1$

Now we need to count three elements subset which contain element $1$.
All those subset will be of the form $\left \{ 1,a,b \right \}$, where $a$ and $b$ are distinct and not equal to $1$.

We can choose all those $a$ and $b$ in $\binom{m-1}{2}$ ways

So, $f(1)=\binom{m-1}{2}$, which is true for any $i$
Therefore, $f(i)=\binom{m-1}{2}$

Now, $$\sum_{i=1}^{m}f(i)=\sum_{i=1}^{m}\binom{m-1}{2}$$
$$=m\binom{m-1}{2}=3\binom{m}{3}=3n$$

Correct Answer: $B$

Comments

nice explaination !!

---

No.of three elements subset = n= mC3
 

Assuming that X1, X2, ... Xn are all  the subsets of S

---

there should be a mathematical correction here.

$\mathbf{\mid S \mid = m}$, where $\color {red} {\mathbf{m > 3}}$

Answer 2

Alternative Approach:

Total elements in $S = m$

Total number of subsets of size $3$ each can be $^{m}c_{3}.$

Now suppose take $1^{st}$ element $1.$ Out of $^{m}c_{3}$ subsets $1$ wont be there in $^{(m-1)}c_{3}$ subsets.

So $1$ will be there in $^{m}c_{3} - ^{(m-1)}c_{3} =\frac{(m-1)(m-2)}{2}$ subsets.

$\sum f(i) =\sum \frac {(m-1)(m-2)}{2} =\frac {m(m-1)(m-2)}{2}.$

We know, $^{m}c_{3} = n$ (No. of $X$ subset)     $\therefore \frac {m(m-1)(m-2)}{2} = 3n.$

Comments

How do we get m(m−1)(m−2)/2=3n

 

how does 3n arrive?

---

This was a nice solution.

Thanks.

---

multiplying 3 on denominator and numerator to make it nC3 as in equation 1.

Answer 3

Number of subsets of size 3 from m elements$\Rightarrow$$m\choose 3$$=n\ \ ....(1)$

$f(i$) is the number of sets $X_{j}$ that contain the element i.

$f(1)=$Number of subsets which contain 1$=$$m-1\choose 2$

$\sum_{i=1}^{m}f(i)=f(1)+f(2)+.......+f(m)=$ $m-1\choose 2$ +$m-1\choose 2$+$m-1\choose 2$+......+$m-1\choose 2$

$m\times$ $m-1\choose 2$ $=m\times \frac{(m-1)(m-2)}{2}=$ $\frac{m(m-1)(m-2)}{2}$

---

From $(1)$

$\frac{m(m-1)(m-2)}{3\times 2}=n$

$\frac{m(m-1)(m-2)}{2}$ $=3n$

Correct Answer: B

Comments

Thanks!

Answer 4

Given that,  S = {1, 2, 3,........, m}, m >3

Total number of elements in S = m

Total number of subsets of size 3 each can be ^mc_3.

Now suppose take 1st element 1. Out of ^mc_{3  subsets}  1 wont be there in ^(m-1)c₃ subsets.

So 1 will be there in ^mc₃ - ^(m-1)c₃ = (m-1)⨉(m-2)/2 subsets. 

Similiarly for all remaining elements 2,3,4,5....m, we have same number of subsets.

i.e. ^mc₃ - ^(m-1)c₃ = (m-1)⨉(m-2)/2

 (from i=1 to m ) ∑f(i) =  (from i=1 to m ) ∑(m-1)⨉(m-2)/2 =  m⨉(m-1)⨉(m-2)/2

In Qs given that  ^mc₃ = n  (No of X subset) ,    therefore m ⨉ (m-1) ⨉ (m-2)/2 = 3n 

The correct answer is,(B) 3n

Comments

What did you achieve by writing the same content as present in the best answer ?

---

In terms of Points:  points for ans + 2 upvotes and One nice comment.:)

My ans is 3 line more than the best ans.

I just want to simplify the answer.I think if anyone simplifies the best answer then it is really helpful for aspirants like me.

---

In many places I saw you just writing answer as "option A" even though best answer has an explanation for option A.

If you are doing it for points then it's pretty much useless.