HMMT 二月 2017 · 冲刺赛 · 第 19 题

HMMT February 2017 — Guts Round — Problem 19

[ 10 ] Find (in terms of n ≥ 1) the number of terms with odd coefficients after expanding the product: ∏ ( x + x ) i j 1 ≤ i<j ≤ n 2 2 2 2 2 2 e.g., for n = 3 the expanded product is given by x x + x x + x x + x x + x x + x x + 2 x x x 2 3 3 1 1 2 1 2 3 1 1 2 2 3 3 and so the answer would be 6.

解析

[ 10 ] Find (in terms of n ≥ 1) the number of terms with odd coefficients after expanding the product: ∏ ( x + x ) i j 1 ≤ i<j ≤ n 2 2 2 2 2 2 e.g., for n = 3 the expanded product is given by x x + x x + x x + x x + x x + x x + 2 x x x 2 3 3 1 1 2 1 2 3 1 1 2 2 3 3 and so the answer would be 6. Proposed by: Sam Korsky Answer: n ! Note that if we take (mod 2), we get that ∏ ∏ ( x + x ) ≡ ( x − x ) = det( M ) , i j j i 1 ≤ i<j ≤ n 1 ≤ i<j ≤ n j − 1 where M is the matrix with M = x . This is called a Vandermonde determinant . Expanding this ij i determinant using the formula n ∑ ∏ i − 1 det( M ) = x , σ ( i ) σ i =1 where the sum if over all n ! permutations σ , gives the result.