Question

Let $S=\{1,2,3,\dots \dots ,m\},m>3$. Let $X_1,X_2,\dots \dots X_n$ be subsets of $S$ each of size $3$. Define a function $f$ from $S$ to the set of natural numbers as $f\left(i\right)$ is the number of sets $X_j$ that contains the element $i$. That is $f\left(i\right)=|\left\{j|iϵX_j\right\}|$. Then $\sum _{i=1}^{m}f\left(i\right)$ is

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

Answer 1

The correct option is B $3n$

The problem can be solved by considering the cases $m=4$ and $m=5$ etc
Let, $m=4$
$S=\{1,2,3,4\}$
$n=$ number of 3 elements subsets
${=}^4{C}_3{=}^4{C}_1=4$
$\therefore n=4$
The 4 subsets are $\{1,2,3\},\{1,2,4\},\{1,3,4\}$ and $\{2,3,4\}$
$f\left(1\right)=$ number of subsets having 1 as an element $=3$
$f\left(2\right)=$ number of subsets having 2 as an element $=3$
$f\left(3\right)=3$ and $f\left(4\right)=3$
$\therefore \sum _{i=1}^{4}f\left(i\right)=3+3+3+3=12$
Both choice (a) and choice (b) are matching the answer since
$3m=3n=12$
Now let us try $m=5$
$S=\{1,2,3,4,5\}$
$n=$ number of 3 element subsets ${=}^5{C}_3=10$
$\therefore 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,5\},\{2,4,5\},\{3,4,5\}$
$f\left(1\right)=f\left(2\right)=f\left(3\right)=f\left(4\right)=f\left(5\right)=6$
$\sum _{i=1}^{5}f\left(i\right)=6+6+6+6+6=30$
Clearly $3m=3\times 5=15\{\text{is not matching}\sum f\left(i\right)\}$
But $3n=3\times 10=30\{\text{is matching}\sum f\left(i\right)=30\}$
$\therefore 3n$ is the only correct answer.
Correct choice is (b)
The problem can also be solved in a more general way as follows:
$\sum _{i=1}^{m}f\left(i\right)=f\left(1\right)+f\left(2\right)+\dots \dots +f\left(m\right)$
Since, $f\left(1\right)=f\left(2\right)=\dots \dots =f\left(m\right){=}^{m-1}{C}_2$
Therefore, $\sum _{i=1}^{m}f\left(i\right)=m{\times }^{(m-1)}{C}_2$
$=\frac{m\times (m-1)\times (m-2)}{2}$
$=\frac{3\times m\times (m-1)\times (m-2)}{1\times 2\times 3}$
$=3{\times }^m{C}_3$
Since $n=$ number of three elements subsets of a set of $m$ elements ${=}^m{C}_3$
Therefore, $\sum _{i=1}^{m}f\left(i\right)=3{\times }^m{C}_3=3n$