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

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.

---

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

---

What a problem. Maza aagaya

Answer 1

So intutive way of thinking is, every set of 3 element (x,y,z) shows increment in corresponding function values.

There are n set and if we sum occurrence of elements due to every set then it would be 3+3+....3 {n times} = 3n 

Answer b) is correct