HMMT 二月 2019 · 冲刺赛 · 第 9 题

HMMT February 2019 — Guts Round — Problem 9

[ 5 ] Define P = { S , T } and let P be the set of all proper subsets of P . (A proper subset is a subset that is not the set itself.) How many ordered pairs ( S , T ) of proper subsets of P are there such that (a) S is not a proper subset of T and T is not a proper subset of S ; and (b) for any sets S ∈ S and T ∈ T , S is not a proper subset of T and T is not a proper subset of S ?

解析

[ 5 ] Define P = { S , T } and let P be the set of all proper subsets of P . (A proper subset is a subset that is not the set itself.) How many ordered pairs ( S , T ) of proper subsets of P are there such that (a) S is not a proper subset of T and T is not a proper subset of S ; and (b) for any sets S ∈ S and T ∈ T , S is not a proper subset of T and T is not a proper subset of S ? Proposed by: Yuan Yao Answer: 7 For ease of notation, we let 0 = ∅ , 1 = { S } , 2 = { T } . Then both S and T are proper subsets of { 0 , 1 , 2 } . We consider the following cases: Case 1. If S = ∅ , then S is a proper subset of anyset except the empty set, so we must have T = ∅ . Case 2. If S = { 0 } , then T cannot be empty, nor can it contain either 1 or 2, so we must have T = { 0 } . This also implies that if S contains another element, then there would be no choice of T because { 0 } would be a proper subset. Case 3. If S = { 1 } , then T cannot contain 0, and cannot contain both 1 and 2 (or it becomes a proper superset of S ), so it can only be { 1 } or { 2 } , and both work. The similar apply when S = { 2 } . Case 4. If S = { 1 , 2 } , then since T cannot contain 0, it must contain both 1 and 2 (or it becomes a proper subset of S ), so T = { 1 , 2 } . Hence, all the possibilities are ( S , T ) = ( ∅ , ∅ ) , ( { 0 } , { 0 } ) , ( { 1 } , { 1 } ) , ( { 1 } , { 2 } ) , ( { 2 } , { 1 } ) , ( { 2 } , { 2 } ) , ( { 1 , 2 } , { 1 , 2 } ) , for 7 possible pairs in total.