5th Irish 1992 Problem A3 A has n elements. How many (B, C) are such that ∅ ≠ B ⊆ C ⊆ A?
3 n Solution There are nCm choices for a subset B with m elements. Then each of the remaining n-m elements can be in C or not, so there are 2 n-m choices for C. Hence the total number of pairs (B,C) is ∑ 2 n-m nCm = ∑ 2 m nCm (since nCm = nCn-m) = (1+2) n = 3 n (by the binomial theorem). 5th Irish 1992 © John Scholes jscholes@kalva.demon.co.uk 4 February 2004 Last updated/corrected 4 Feb 04