HMMT 二月 2015 · 冲刺赛 · 第 35 题

英文解析

35. [ 25 ] Let P denote the set of all subsets of { 1 , . . . , 23 } . A subset S ⊆ P is called good if whenever A, Bare sets in S , the set ( A \ B ) ∪ ( B \ A ) is also in S . (Here, A \ B denotes the set of all elements in Athat are not in B , and B \ A denotes the set of all elements in B that are not in A .) What fractionof the good subsets of P have between 2015 and 3015 elements, inclusive?
    If your answer is a decimal number or a fraction (of the form m/n , where m and n are positive integers),
    then your score on this problem will be equal to max { 0 , 25 − ⌊ 1000 | A − N |⌋} , where N is your answerand A is the actual answer. Otherwise, your score will be zero.
    18839183877670041942218307147122500601235
    Answer: ≈ 0 . 3950203047068107 Let n = 23, and ℓ =
    47691684840486192422095701784512492731212
    ⌊ n/ 2 ⌋ = 11.
    We use the well-known rephrasing of the symmetric difference (( A \ B ) ∪ ( B \ A )) in terms of addition
    ( )
    modulo 2 of “indicators/characteristic vectors”. So we simply want the number of dimension ℓnℓn d 2
    subspaces of the F := F -vector space V := F . Indeed, good subsets of 2 elements simply correspondto dimension d subspaces (in particular, good subsets can only have sizes equal to powers of | F | = 2,22
    and 2 is the only power between 2015 and 3015, inclusive).ℓ
    To do this, it’s easier to first count the number of (ordered) tuples of ℓ linearly independent elements of
    V , and divide (to get the subspace count) by the number of (ordered) tuples of ℓ linearly independentelements of any ℓ -dimensional subspace of V (a well-defined number independent of the choice ofsubspace).
    In general, if we want to count tuples of m linearly independent elements in an n -dimensional space
    (with n ≥ m ), just note that we are building on top of (0) (the zero-dimensional subspace), and oncen rwe’ve chosen r ≤ m elements (with 0 ≤ r ≤ m − 1), there are 2 − 2 elements linearly independentrto the previous r elements (which span a subspace of dimension r , hence of 2 “bad” elements). Thusthe number of m -dimensional subspaces of an n -dimensional space is
    ( )
    n 0 n 1 n m − 1
    n (2 − 2 )(2 − 2 ) · · · (2 − 2 )
    := ,
    m 0 m 1 m m − 1
    m (2 − 2 )(2 − 2 ) · · · (2 − 2 )
    a “Gaussian binomial coefficient.”2
    We want to estimate
    ( ) ( )
    n 23
    ℓ 111
    2 2
    ( )
    ∑ = .
    ( )
    ∑
    11 nnm =0223
    2 m =0 mm
    ( ) ( )2
    n n
    To do this, note that = , so we may restrict our attention to the lower half. Intuitively, them n − m
    Gaussian binomial coefficients should decay exponentially (or similarly quickly) away from the center;22
    indeed, if m ≤ n/ 2, then
    ( ) ( )
    m 0 m − 1
    n n (2 − 2 ) · 2
    2 m − 1 − n / = ≈ 2 .
    n m − 1
    m − 1 m (2 − 2 )
    2 2
    So in fact, the decay is super-exponential, starting (for n = 23 odd and m ≤ ℓ = 11) at an ≈ rate.1
    So most of the terms (past the first 2 to 4, say) are negligible in our estimation. If we use the first two 4
    1 1 2
    terms, we get an approximation of · = = 0 . 4, which is enough for 20 points. (Including the
    2 51
    1+
    next term gives an approximation of ≈ 0 . 3950617, which is good enough to get full credit.)324
    To compute the exact answer, we used the following python 3 code:81
    Gutsfrom functools import lru_cachefrom fractions import Fraction
    @lru_cache(maxsize=None)
    def gauss_binom(n, k, e):
    if k < 0 or k > n:
    return 0
    if k == 0 or k == n:
    return 1
    return e ** k * gauss_binom(n - 1, k, e) +
    gauss_binom(n - 1, k - 1, e)
    N = 23
    K = 11
    good = gauss_binom(N, K, 2)
    total = sum(gauss_binom(N, i, 2) for i in range(N + 1))
    print(Fraction(good, total))
    print(float(good/total))