HMMT 十一月 2010 · 冲刺赛 · 第 6 题

HMMT November 2010 — Guts Round — Problem 6

[ 6 ] How many ordered pairs ( S, T ) of subsets of { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 } are there whose union contains exactly three elements? 2 2

解析

[ 6 ] How many ordered pairs ( S, T ) of subsets of { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 } are there whose union contains exactly three elements? Answer: 3240 Let the three elements in the union be a , b , and c . We know that a can be only in S , only in T , or both, so there are 3 possibilities for placing it. (Recall that S = { a } , T = { b, c } is different from S = { b, c } , T = { a } because S and T are an ordered pair.) Likewise for b and c . The other 7 elements are in neither S nor T , so there is only 1 possibility for placing them. This gives ( ) 10 3 3 = 27 ways to pick S and T once you’ve picked the union. There are = 120 ways to pick the 3 elements in the union, so we have 120 × 27 = 3240 ways total. 2 2