HMMT 二月 2014 · COMB 赛 · 第 4 题
HMMT February 2014 — COMB Round — Problem 4
题目详情
- Find the number of triples of sets ( A, B, C ) such that: (a) A, B, C ✓ { 1 , 2 , 3 , . . . , 8 } . (b) | A \ B | = | B \ C | = | C \ A | = 2. (c) | A | = | B | = | C | = 4. Here, | S | denotes the number of elements in the set S .
解析
- Find the number of triples of sets ( A, B, C ) such that: (a) A, B, C ⊆ { 1 , 2 , 3 , . . . , 8 } . (b) | A ∩ B | = | B ∩ C | = | C ∩ A | = 2. (c) | A | = | B | = | C | = 4. Here, | S | denotes the number of elements in the set S . Answer: 45360 We consider the sets drawn in a Venn diagram. A R 1 R R 6 5 R 7 R R 2 3 R 4 B C Note that each element that is in at least one of the subsets lies in these seven possible spaces. We split by casework, with the cases based on N = | R | = | A ∩ B ∩ C | . 7 Case 1: N = 2 Because we are given that | R | + N = | R | + N = | R | + N = 2, we must have | R | = | R | = | R | = 0. 4 5 6 4 5 6 But we also know that | R | + | R | + | R | + N = 4, so | R | = 2. Similarly, | R | = | R | = 2. Since these 1 5 6 1 2 3 ( )( )( )( ) 8 6 4 2 regions are distinguishable, we multiply through and obtain = 2520 ways. 2 2 2 2 Case 2: N = 1 In this case, we can immediately deduce | R | = | R | = | R | = 1. From this, it follows that | R | = 4 5 6 1 4 − 1 − 1 − 1 = 1, and similarly, | R | = | R | = 1. All seven regions each contain one integer, so there 2 3 are a total of (8)(7) . . . (2) = 40320 ways. Case 3: N = 0 Because | R | + N = | R | + N = | R | + N = 2, we must have | R | = | R | = | R | = 2. Since 4 5 6 4 5 6 | R | + | R | + | R | + N = 4, we immediately see that | R | = 0. Similarly, | R | = | R | = 0. The number 1 5 6 1 2 3 ( )( )( ) 8 6 4 of ways to fill R , R , R is = 2520. 4 5 6 2 2 2 This clearly exhausts all the possibilities, so adding gives us 40320 + 2520 + 2520 = 45360 ways.