返回题库

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

HMMT February 2017 — Guts Round — Problem 19

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. [ 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.
解析

英文解析

  1. [ 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.