PUMaC 2020 · 组合（B 组） · 第 5 题
PUMaC 2020 — Combinatorics (Division B) — Problem 5
题目详情
- Let P be the power set of { 1 , 2 , 3 , 4 } (meaning the elements of P are the subsets of { 1 , 2 , 3 , 4 } ). How many subsets S of P are there such that no two distinct integers a, b ∈ { 1 , 2 , 3 , 4 } appear together in exactly one element of S ?
解析
- Let P be the power set of { 1 , 2 , 3 , 4 } (meaning the elements of P are the subsets of { 1 , 2 , 3 , 4 } ). How many subsets S of P are there such that no two distinct integers a, b ∈ { 1 , 2 , 3 , 4 } appear together in exactly one element of S ? Proposed by Austen Mazenko Answer: 21056 . Solution: First, notice that whether or not ∅ , { 1 } , { 2 } , { 3 } , { 4 } are in S does not affect the 5 pairing condition, so we multiply by 2 at the end to account for all possible cases where only some of these are in S . Now suppose { 1 , 2 , 3 , 4 } ∈ S . Thus, every pair of elements a, b ∈ { 1 , 2 , 3 , 4 } appears together in at least one element of S , so they must appear in another. If S has at least two elements of cardinality 3, then this condition is satisfied. There are 11 ways to assign at least two such 6 elements to S , then 2 ways to determine which sets of cardinality 2 are elements of S , giving 6 11 · 2 in this case. If S has at least three elements of cardinality 3, then this condition is satisfied. There are 6 5 ways to assign at least three such elements to S , then 2 ways to determine which sets of 6 cardinality 2 are elements of S , giving 5 · 2 in this case. If it has two elements of cardinality 3, WLOG they’re 1,2,3 and 2,3,4: note this may be picked 6 ways. Then, 1,4 must be in S while 5 5 the remaining five sets of cardinality 2 can be assigned in 2 ways, giving 6 · 2 possibilities. If it has only one, WLOG it’s { 1 , 2 , 3 } . Thus, we need { 1 , 4 } , { 2 , 4 } , { 3 , 4 } to all be elements of 3 S . It doesn’t matter if the remaining three sets of cardinality 2 are in S , so we have 2 ways 5 to assign them; multiplying by 4 to account for the WLOG assumption gives 2 . If S has no 2 elements of cardinality 3, then every possible set of cardinality 2 must be in S , giving 1 case. Otherwise, { 1 , 2 , 3 , 4 } ∈ / S , so we do casework on the number of three-element sets that are elements of S . If all four are elements of S , then each pair of integers occurs in at least two of them, so we 6 may arbitrarily assign the sets of cardinality 2 in 2 ways. If only three are elements of S , we may choose them 4 ways. Then, WLOG { 1 , 2 , 3 } ∈ / S , so 3 { 1 , 2 } , { 1 , 3 } , { 2 , 3 } ∈ S and we may decide to add the other cardinality 2 sets into S in 2 3 5 ways, giving 4 · 2 = 2 in this case. If only two are elements of S , we may choose them 6 ways. Then, only a single pair will have occurred twice, so we may either include the two-element subset with this pair or not, giving 2 · 6 = 12 total cases. If only one is an element of S , which may be chosen 4 ways, then all the others are fixed. If none are elements of S , then none of the two-element subsets may be elements of S giving 1 case in this situation. 6 5 5 6 5 Tallying our above count gives 5 · 2 + 6 · 2 + 2 + 1 + 2 + 2 + 12 + 4 + 1 = 658, which 5 multiplied by 2 gives 21056.