HMMT 二月 2010 · 冲刺赛 · 第 30 题
HMMT February 2010 — Guts Round — Problem 30
题目详情
- [ 18 ] A monomial term x x . . . x in the variables x , x , . . . x is square-free if i , i , . . . i are distinct. i i i 1 2 8 1 2 k 1 2 k (A constant term such as 1 is considered square-free.) What is the sum of the coefficients of the square- free terms in the following product? ∏ (1 + x x ) i j 1 ≤ i<j ≤ 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . th 13 ANNUAL HARVARD-MIT MATHEMATICS TOURNAMENT, 20 FEBRUARY 2010 — GUTS ROUND
解析
- [ 18 ] A monomial term x x . . . x in the variables x , x , . . . x is square-free if i , i , . . . i are distinct. i i i 1 2 8 1 2 k 1 2 k (A constant term such as 1 is considered square-free.) What is the sum of the coefficients of the square- free terms in the following product? ∏ (1 + x x ) i j 1 ≤ i<j ≤ 8 4 See http://en.wikipedia.org/wiki/Chinese_remainder_theorem . 5 See http://en.wikipedia.org/wiki/Fermat’s_little_theorem . Guts Round ∏ Answer: 764 Let a be the sum of the coefficients of the square-terms in the product (1 + n 1 ≤ i<j ≤ n x x ). Square-free terms in this product come in two types: either they include x , or they do not. i j n The sum of the coefficients of the terms that include x is ( n − 1) a , since we can choose any n n − 2 of the n − 1 other variables to be paired with x , and then choose any square-free term from the n product taken over the other n − 2 variables. The sum of the coefficients of the terms that do not include x are a , because they all come from the product over the other n − 1 variables. Therefore, n n − 1 a = a + ( n − 1) a . n n − 1 n − 2 We use this recursion to find a . As base cases, a and a are both 1. Then a = 2, a = 4, a = 10, 8 0 1 2 3 4 a = 26, a = 76, a = 232, and finally, a = 764. 5 6 7 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . th 13 ANNUAL HARVARD-MIT MATHEMATICS TOURNAMENT, 20 FEBRUARY 2010 — GUTS ROUND