HMMT 二月 2013 · 冲刺赛 · 第 29 题

英文解析

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 mthat 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 eachi
    2012
    ( )
    a + bof the sets B contain b elements, then the maximum value for m is .
    Let U denote the union of all the sets A and B and let | U | = n . Consider the n ! orderings of theaji jelements of U . Note that for any specific ordering, there is at most one value of i such that all theelements in A come before all the elements in B in this ordering; this follows since A shares at leasti i jone 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 thei ielements in A come first is equal to a ! b !. Therefore, the number of permutations of U where all theielements in A come before all the elements in B is equal to:
    i ia ! b ! n !
    n ! · = ( )
    a + b
    ( a + b )!
    Summing over all m values of i , the total number of orderings where, for some i , the elements in Aaicome before B is equal toi
    Guts Roundn ! m
    ( )
    a + ba
    ( )
    a + b
    But there are at most u ! such orderings, since there are u ! total orderings, so it follows that m ≤ .
    Equality is attained by taking U to be a set containing ( a + b ) elements, letting A range over allaia -element subsets of U , and letting B = U \ A for each i .
    i i