HMMT 二月 2013 · 冲刺赛 · 第 29 题
HMMT February 2013 — Guts Round — Problem 29
题目详情
- [ 20 ] Let A , A , ..., A be finite sets of size 2012 and let B , B , ..., B be finite sets of size 2013 such 1 2 m 1 2 m that A ∩ B = ∅ if and only if i = j . Find the maximum value of m . i j
解析
- [ 20 ] Let A , A , ..., A be finite sets of size 2012 and let B , B , ..., B be finite sets of size 2013 such 1 2 m 1 2 m that A ∩ B = ∅ if and only if i = j . Find the maximum value of m . i j ( ) 4025 Answer: In general, we will show that if each of the sets A contain a elements and if each i 2012 ( ) a + b of the sets B contain b elements, then the maximum value for m is . j a Let U denote the union of all the sets A and B and let | U | = n . Consider the n ! orderings of the i j elements of U . Note that for any specific ordering, there is at most one value of i such that all the elements in A come before all the elements in B in this ordering; this follows since A shares at least i i j one element with B and B shares at least one element with A for any other j 6 = i . i j i On the other hand, the number of ways to permute the ( a + b ) elements in A ∪ B so that all the i i elements in A come first is equal to a ! b !. Therefore, the number of permutations of U where all the i elements in A come before all the elements in B is equal to: i i a ! b ! n ! n ! · = ( ) a + b ( a + b )! a Summing over all m values of i , the total number of orderings where, for some i , the elements in A i come before B is equal to i Guts Round n ! m ( ) a + b a ( ) a + b But there are at most u ! such orderings, since there are u ! total orderings, so it follows that m ≤ . a Equality is attained by taking U to be a set containing ( a + b ) elements, letting A range over all i a -element subsets of U , and letting B = U \ A for each i . i i