Skip to content
GATETECH
Official PYQ · 2006Q25Sets, Relations and FunctionsMCQ1 mark

GATE CS 2006 Q25 — Sets, Relations and Functions

Explain with AI

Let S={1,2,3,…,m},m>3.S = \{1, 2, 3,\ldots, m\}, m >3. Let X1,…,XnX_1,\ldots,X_n be subsets of SS each of size 3.3. Define a function ff from SS to the set of natural numbers as, f(i)f(i) is the number of sets XjX_j that contain the element i.i. That is f(i)=∣{j∣i∈Xj}∣f(i)=\left | \left\{j \mid i\in X_j \right\} \right|   then ∑i=1mf(i)\sum_{i=1}^{m} f(i) is:

Choose one option
View worked solution

Answer: B

We are given a set S={1,2,3,…,m}S = \{1, 2, 3, \ldots, m\} and nn subsets X1,X2,…,XnX_1, X_2, \ldots, X_n of SS, each of size 33 (i.e., ∣Xj∣=3|X_j| = 3 for all 1≤j≤n1 \le j \le n).

The function f(i)f(i) represents the number of subsets XjX_j that contain the element ii. Mathematically, this can be written using an indicator function:

f(i)=∑j=1n[i∈Xj]f(i) = \sum_{j=1}^{n} [i \in X_j]

where [i∈Xj][i \in X_j] is 11 if i∈Xji \in X_j, and 00 otherwise.

We need to find the sum ∑i=1mf(i)\sum_{i=1}^{m} f(i):

∑i=1mf(i)=∑i=1m∑j=1n[i∈Xj]\sum_{i=1}^{m} f(i) = \sum_{i=1}^{m} \sum_{j=1}^{n} [i \in X_j]

By swapping the order of summation, we get:

∑i=1mf(i)=∑j=1n∑i=1m[i∈Xj]\sum_{i=1}^{m} f(i) = \sum_{j=1}^{n} \sum_{i=1}^{m} [i \in X_j]

For a fixed subset XjX_j, the inner sum ∑i=1m[i∈Xj]\sum_{i=1}^{m} [i \in X_j] simply counts the number of elements in XjX_j. Since each subset XjX_j has exactly 33 elements, we have:

∑i=1m[i∈Xj]=∣Xj∣=3\sum_{i=1}^{m} [i \in X_j] = |X_j| = 3

Substituting this back into the equation:

∑i=1mf(i)=∑j=1n3=3n\sum_{i=1}^{m} f(i) = \sum_{j=1}^{n} 3 = 3n

Therefore, the correct option is B.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Sets, Relations and Functions questions