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

BEST METHOD

 

The problem can be solved by considering the cases m=5 

let us try m=5
S={1,2,3,4,5}
 

n= number of 3 element subsets =5C3=10
∴n=10
The 10 subsets are {1,2,3}, {1,2,4}, {1,2,5},{1,3,4}, {1,3,5}, {1,4,5},{2,3,4}{2,3,5}, {2,4,5}, {3,4,5}

so f(1)=f(2)=f(3)=f(4)=f(5)=6
 

5∑i=1f(i)=6+6+6+6+6=30
Clearly 3m=3×5=15{is not matching ∑f(i)}
But 3n=3×10=30 {is matching ∑f(i)=30}
∴3n is the only correct answer.

Correct choice is (b)
 

Answer 2

i certainly do not think that the question ever intended us to assume that we should take every 3 element subset of a set of order m.

 

let s={1,2,3,4},  order=4=m,  4>3

subsets =>  s1: 123;   s2:124 ;     no. of subsets 2=n

even for this the given statement holds that summation of f(i)=3*n=3*2=6 (2 times 1, 2 times 2, 1 time 3, 1 time 4)

 

 

more generally,

let S={1,2,3,......,m};   m>k

let X1,X2,X3,....,Xn be subsets of X ,each of size k (not necessarily all subsets of size k)

"Define a function f from S to the set of natural numbers as, f(i) is the number of sets Xj that contain the element i"

then,

  [i from 1 to m] ∑f(i) = k*n

Answer 3

First of all, number of subsets of S of size 3 is mC3 i.e. n=mC3. Now we count number of subsets in which a particular element i appears, that will be (m−1)C2, because 1 element is already known, and we have to choose 2 elements from remaining m-1 elements.

 

https://www.geeksforgeeks.org/gate-gate-cs-2006-question-25/

Answer 4

There are total of n subsets. Each subset contains three element, so one particular subset will be counted thrice. 

For example if set is (a,b,c), then it will contribute to f(a), f(b), and f(c ) . 

Thus 3*n i.e 3n (and).