Let S = {1, 2, 3, ...., m}, m>3. Let X1, X2, ..., Xn be the subsets of S each…
2006
Let S = {1, 2, 3, ...., m}, m>3. Let X1, X2, ..., Xn be the 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 Xj that contain the element i. That is, f(i) = |{j | i ϵ Xj}| then
- A.
3m
- B.
3n
- C.
2m + 1
- D.
2n + 1
Attempted by 102 students.
Show answer & explanation
Correct answer: B
Concept: A double-counting argument: when a collection of n sets is examined element by element, summing each element's own count of “how many sets contain it” over every element gives exactly the same total as summing the size of each set over all n sets. The same set of (element, set) pairs is simply grouped two different ways — once by element, once by set — so both groupings must total to the same number.
Application: Apply this to f(i), the number of subsets Xj containing element i:
Summing f(i) over every element i of S counts each pair (element, subset) exactly once — once for every subset that the element belongs to.
Grouping those same pairs by subset instead: each of the n subsets Xj has exactly 3 elements, so each subset contributes exactly 3 pairs.
Across all n subsets, the total number of pairs is therefore n × 3.
Cross-check: Take m = 5, n = 2 with X1 = {1,2,3}, X2 = {3,4,5}. Then f(1)=1, f(2)=1, f(3)=2, f(4)=1, f(5)=1, and the sum is 1+1+2+1+1 = 6, matching n × 3 = 2 × 3 = 6 — the same value the counting argument gives in general (and clearly distinct from the other offered expressions for this m, n).
So the sum over i of f(i) is 3n.