HMMT 二月 2017 · 冲刺赛 · 第 7 题

英文解析

7. [ 6 ] An ordered pair of sets ( A, B ) is good if A is not a subset of B and B is not a subset of A . Howmany ordered pairs of subsets of { 1 , 2 , . . . , 2017 } are good?
   Proposed by: Alexander Katz
   2017 2017 2017
   Answer: 4 − 2 · 3 + 2
   2017
   Firstly, there are 4 possible pairs of subsets, as each of the 2017 elements can be in neither subset,
   in A only, in B only, or in both.
   Now let us count the number of pairs of subsets for which A is a subset of B . Under these conditions,
   2017
   each of the 2017 elements could be in neither subset, in B only, or in both A and B . So there are 3
   such pairs.
   2017
   By symmetry, there are also 3 pairs of subsets where B is a subset of A . But this overcounts the
   2017
   pairs in which A is a subset of B and B is a subset of A , i.e. A = B . There are 2 such subsets.
   2017 2017 2017
   Thus, in total, there are 4 − 2 · 3 + 2 good pairs of subsets.