Let S = {1, 2, 3, ..., m}, m 3. Let X_1, ..., X_n be subsets of S each of size 3. Define a function f from S to the se...

Question

Let S = {1, 2, 3, ..., m}, m > 3. Let X_1, ..., 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) = |{j | i in X_j}|, then sum_{i=1}^{m} f(i) is: A. 3m  B. 3n  C. 2m + 1  D. 2n + 1

Accepted Answer

sum_{i=1}^{m} f(i) = 3n, so the answer is Option B. f(i) counts how many of the n subsets contain element i. Summing f(i) over all m elements counts, in total, every (element, set) membership pair across all the subsets. But we can count the same pairs the other way: each of the n subsets has exactly 3 elements, so it contributes 3 memberships. Adding over the n subsets gives 3n. This double counting trick makes the sum 3n regardless of m.