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 ≤ nj − 1
where M is the matrix with M = x . This is called a Vandermonde determinant . Expanding thisijdeterminant using the formulain
∑ ∏
i − 1
det( M ) = x ,
σ ( i )
σ i =1
where the sum if over all n ! permutations σ , gives the result.