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

can someone plz explain with an example taking n=4

---

here we can take m not n because n is number of subset.

take m= 4 {1,2,3,4}

make 3 elemnt subset = {1,2,3} {1,3,4} {2,3,4}, {1,2,4}

n = 4 i.e. number of subset  question said f(i) = number of time i i appear in different set.

so add for each element i.e. f(1) +f(2)+f(3)+f(4) = 3+3+3+3= 12

---

@manoj how this line comes 

∑f(i) =  ∑(m-1)(m-2)/2 =  m(m-1)(m-2)/2

---

for 1 element (m-1)(m-2)/2 subsets

for m  "           m (m-1)(m-2)/2 "

but imp part is here ^mc₃ - ^(m-1)c₃

which we can formulate only by taking example

---

someone plz explain why 3m is not the answer. i is from 1 to m and we are adding 3, m times so it should be 3m.

---

@vineet

"f(i) is the number of sets X_j that contain the element i" , Here it says number of subsets that contain element 'i' and summation explains total number of subsets that contain that particular element 'i' (f(i)) and  'm' represents elements and 'n' is the number of subsets and each subset size is 3 so ∑f(i) = 3n

---

For those who are wondering how to calculate

$$f(i)=\binom{m}{3}-\binom{m-1}{3}$$

One way is to expand and simplify and another way is to apply Pascal's triangle

From Pascal's triangle, we know

$$\binom{n}{k-1}+\binom{n}{k}=\binom{n+1}{k}$$

$$or,\binom{n+1}{k}-\binom{n}{k}=\binom{n}{k-1}$$

Applying this formula, we get

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

PS: Well there is an alternative way to find $f(i)$

---

vineet.ildm you are confused because in Prashant.'s example there were 4 elements and 4 subsets but that's not the case when you take size of S more than 4 

if you take S = {1,2,3,4,5}

there will be $\binom{5}{3}$ = 10 subsets of cardinality 3

and 1 will appear in $\binom{4}{2}$ = 6 subsets 

and similarly other 4 elements of S making sum = 5 * 6 = 30 

which is 3n = 3 * 10 = 30

---

@Mk Utkarsh yes this is one of the problem when we try to take an example and solve. 

https://gateoverflow.in/2083/gate2014-3-49 like this question. Answer changes according to cardinality of the set.

But with practice you can overcome this by satisfying the criteria in question like:

1: m>3

2: getting conflict when m and n =4 as both a,b results in 12.

3 : go with m =5 and you can eliminate options.

Though it looks lengthy, it won't take much time and you will be sure about answer. :) 

---

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.