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 squarefree terms in the following product?
∏
(1 + x x )
i j
1 ≤ i<j ≤ 8
13 ANNUAL HARVARD-MIT MATHEMATICS TOURNAMENT, 20 FEBRUARY 2010 — GUTS ROUNDth
解析
英文解析
- [ 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
(A constant term such as 1 is considered square-free.) What is the sum of the coefficients of the square-kfree terms in the following product?
∏
(1 + x x )
i j
1 ≤ i<j ≤ 8
See http://en.wikipedia.org/wiki/Chinese_remainder_theorem .4
See http://en.wikipedia.org/wiki/Fermat’s_little_theorem .5
Guts Round
∏
Answer: 764 Let a be the sum of the coefficients of the square-terms in the product (1 +
1 ≤ i<j ≤ nnx 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 anyn n − 2
of the n − 1 other variables to be paired with x , and then choose any square-free term from thenproduct taken over the other n − 2 variables. The sum of the coefficients of the terms that do notinclude 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
13 ANNUAL HARVARD-MIT MATHEMATICS TOURNAMENT, 20 FEBRUARY 2010 — GUTS ROUNDth