PUMaC 2022 · 组合（A 组） · 第 7 题
PUMaC 2022 — Combinatorics (Division A) — Problem 7
题目详情
- Kelvin has a set of eight vertices. For each pair of distinct vertices, Kelvin independently draws an edge between them with probability p ∈ (0 , 1). A set S of four distinct vertices is called good if there exists an edge between v and w for all v, w ∈ S with v ̸ = w . The variance of the number of good sets can be expressed as a polynomial f ( p ) in the variable p . Find the sum of the absolute values of the coefficients of f ( p ). 2 2 (The variance of random variable X is defined as E [ X ] − E [ X ] .) 1
解析
- Kelvin has a set of eight vertices. For each pair of distinct vertices, Kelvin independently draws an edge between them with probability p ∈ (0 , 1). A set S of four distinct vertices is called good if there exists an edge between v and w for all v, w ∈ S with v ̸ = w . The variance of the number of good sets can be expressed as a polynomial f ( p ) in the variable p . Find the sum of the absolute values of the coefficients of f ( p ). 2 2 (The variance of random variable X is defined as E [ X ] − E [ X ] .) Proposed by Sunay Joshi Answer: 7420 For convenience, let n = 8 and let X denote the number of good subsets. Note that X = P I , where I denotes the indicator random variable that S is a good subset, and where S S | S | =4 the sum runs over all subsets of size 4. Writing Var( X ) = Cov( X, X ) and expanding using bilinearity, we find X X Var( X ) = Var( I ) + 2 Cov( I , I ) , S S T | S | =4 | S | , | T | =4 ,S ̸ = T where the second sum runs over all pairs of distinct sets S, T of size 4. Since Var( I ) = S 2 6 6 12 P (S good) − P (S good) and since P (S good) = p , we have Var( I ) = p − p . We now consider S the second sum. Note that Cov( I , I ) = P (S and T good) − P (S good) P (T good). From the S T 12 11 above, this reduces to P (S and T good) − p . If | S ∩ T | = 2, then P (S and T good) = p , n n − 2 n − 4 1 9 and there are · such pairs. If | S ∩ T | = 3, then P (S and T good) = p , and 2 2 2 2 n n − 3 there are such pairs. Plugging this into our sum, we find 3 2 n n n − 2 n − 4 1 n n − 3 6 12 11 12 9 12 Var( X ) = ( p − p ) + 2 · ( p − p ) + ( p − p ) 4 2 2 2 2 3 2 Rewriting, we find the polynomial n n n − 2 n − 4 n n − 3 n n − 2 n − 4 12 11 f ( p ) = − p + + 2 + p 4 2 2 2 3 2 2 2 2 n n − 3 n 9 6
- p 2 + p 3 2 4 Plugging in n = 8 and summing the absolute values of the coefficients, we find 7420, our answer. 4