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

HMMT February 2017 — Guts Round — Problem 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 . How many ordered pairs of subsets of { 1 , 2 , . . . , 2017 } are good?

解析

[ 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 . How many 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.