HMMT 二月 2014 · COMB 赛 · 第 4 题

英文解析

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 .
   Answer: 45360 We consider the sets drawn in a Venn diagram.
   1RA
   R R
   6 5
   7R
   R R
   2 3
   4R
   B C
   Note that each element that is in at least one of the subsets lies in these seven possible spaces. Wesplit by casework, with the cases based on N = | R | = | A ∩ B ∩ C | .
   Case 1: N = 27
   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.