HMMT 二月 2015 · 冲刺赛 · 第 35 题
HMMT February 2015 — Guts Round — Problem 35
题目详情
- [ 25 ] Let P denote the set of all subsets of { 1 , . . . , 23 } . A subset S ⊆ P is called good if whenever A, B are sets in S , the set ( A \ B ) ∪ ( B \ A ) is also in S . (Here, A \ B denotes the set of all elements in A that are not in B , and B \ A denotes the set of all elements in B that are not in A .) What fraction of 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 answer and A is the actual answer. Otherwise, your score will be zero.
解析
- [ 25 ] Let P denote the set of all subsets of { 1 , . . . , 23 } . A subset S ⊆ P is called good if whenever A, B
are sets in S , the set ( A \ B ) ∪ ( B \ A ) is also in S . (Here, A \ B denotes the set of all elements in A
that are not in B , and B \ A denotes the set of all elements in B that are not in A .) What fraction
of 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 answer
and 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
( )
n
modulo 2 of “indicators/characteristic vectors”. So we simply want the number of dimension ℓ
ℓ
2
n d
subspaces of the F := F -vector space V := F . Indeed, good subsets of 2 elements simply correspond
2
2
to dimension d subspaces (in particular, good subsets can only have sizes equal to powers of | F | = 2,
ℓ
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 independent
elements of any ℓ -dimensional subspace of V (a well-defined number independent of the choice of
subspace).
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 once
n r
we’ve chosen r ≤ m elements (with 0 ≤ r ≤ m − 1), there are 2 − 2 elements linearly independent
r
to the previous r elements (which span a subspace of dimension r , hence of 2 “bad” elements). Thus
the 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 )
2
a “Gaussian binomial coefficient.”
We want to estimate
( ) ( )
n 23
1
ℓ 11
2 2
( )
∑ = .
( )
∑
n
n
11
23
2
m =0
m
2 m =0
m
2
( ) ( )
n n
To do this, note that = , so we may restrict our attention to the lower half. Intuitively, the
m n − m
2
2
Gaussian binomial coefficients should decay exponentially (or similarly quickly) away from the center;
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
1
So in fact, the decay is super-exponential, starting (for n = 23 odd and m ≤ ℓ = 11) at an ≈ rate.
4
So most of the terms (past the first 2 to 4, say) are negligible in our estimation. If we use the first two
1 1 2
terms, we get an approximation of · = = 0 . 4, which is enough for 20 points. (Including the
1
2 5
1+
4
32
next term gives an approximation of ≈ 0 . 3950617, which is good enough to get full credit.)
81
To compute the exact answer, we used the following python3 code:
Guts
from functools import lru_cache
from 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))