Solution
Sum of the Minima
Show the problem again
For each of the C(10, 3) = 120 three-element subsets of {1, 2, ..., 10}, write down its smallest element. What is the sum of all 120 numbers written? Give an integer.
Worked solution
The answer is 330. A subset {m < b < c} contributes m, which we can think of as m "tokens" labelled j = 1, ..., m. So the sum counts pairs (j, S) with S a 3-subset of {1, ..., 10} and 1 ≤ j ≤ min S. Map such a pair to the 4-element set {j, m + 1, b + 1, c + 1} ⊆ {1, ..., 11}. Since j ≤ m < m + 1, this set has smallest element j, and from any 4-subset {w < x < y < z} of {1, ..., 11} we recover j = w and S = {x − 1, y − 1, z − 1}, with w ≤ x − 1 automatically. So the map is a bijection and the sum equals C(11, 4) = 330. (Equivalently, the expected minimum of a random 3-subset of {1, ..., 10} is 330/120 = 11/4.)
Source: Classic counting exercise in wide circulation; no traceable original source. Statement written for AxiomIQ.