HMMT 十一月 2019 · 冲刺赛 · 第 34 题
HMMT November 2019 — Guts Round — Problem 34
题目详情
- [20] A polynomial P with integer coefficients is called tricky if it has 4 as a root. A polynomial is called k - tiny if it has degree at most 7 and integer coefficients between − k and k , inclusive. A polynomial is called nearly tricky if it is the sum of a tricky polynomial and a 1-tiny polynomial. Let N be the number of nearly tricky 7-tiny polynomials. Estimate N . ⌊ ⌋ ( ) 4 N E An estimate of E will earn 20 min , points. E N
解析
- [20] A polynomial P with integer coefficients is called tricky if it has 4 as a root.
A polynomial is called k - tiny if it has degree at most 7 and integer coefficients between − k and k ,
inclusive.
A polynomial is called nearly tricky if it is the sum of a tricky polynomial and a 1-tiny polynomial.
Let N be the number of nearly tricky 7-tiny polynomials. Estimate N .
⌊ ⌋
( )
4
N E
An estimate of E will earn 20 min , points.
E N
Proposed by: Carl Schildkraut
Answer: 64912347
A tricky 7-tiny polynomial takes the form
6
( c x + . . . + c x + c )( x − 4) .
6 1 0
For each fixed value of k , c − 4 c should lie in [ − 7 , 7], so if we fix c , there are around 15 / 4 ways
k k +1 k
7
of choosing c . Therefore if we pick c , . . . , c in this order, there should be around (15 / 4) tricky
k +1 0 6
7-tiny polynomials.
7 8
A 1-tiny polynomial takes the form ε x + · · · + ε x + ε with ε ∈ {− 1 , 0 , +1 } , so there are 3 1-tiny
6 1 0 i
polynomials.
A nearly tricky 7-tiny polynomial P takes the form Q + T where Q is roughly a tricky 7-tiny polynomial,
and T is 1-tiny. Furthermore, there is a unique decomposition Q + T because T (4) = P (4) and each
∑
k
integer n can be written in the form ε 4 in at most one way. Therefore the number of nearly tricky
k
7 8
7-tiny is around (15 / 4) · 3 ≈ 68420920, which is worth 16 points.
The exact answer can be found by setting up recurrences. Let t ( d,
) be the number of polynomials of degree at most i of the form d − 1 d − 2 d − 1 (x + c x + · · · + c )( x − 4) + ( ε x + · · · + ε x + ε ) . d − 2 0 d − 1 1 0 d which has integer coefficients between − 7 and 7 except the leading termx . It follows that t (0 , 0) = 1 , t (0 , k ) = 0 for all k 6 = 0, and t ( d + 1 ,) can be computed as follows: for each value of c , there are d − 1 t ( d, c ) ways to pick c , . . . , c , ε , . . . , ε , and exactly w ( c − 4) ways of picking ε , where d − 1 d − 2 0 d − 1 0 d − 1 d w ( k ) = min(9 − | k | , 3) for | k | ≤ 8 and 0 otherwise. Therefore setting c = c − 4we have d − 1 8 ∑ t ( d + 1 , ` ) = t ( d, c + 4 ` ) w ( c ) . c = − 8 The number of nearly tricky 7-tiny polynomials is simply t (8 , 0), which can be computed to be 64912347 using the following C code. int w(int a){ if(a < -9 || a > 9) return 0; else if(a == -8 || a == 8) return 1; else if(a == -7 || a == 7) return 2; else return 3; } int main() { int m=8,n=7,r=4,d,l,c,c4l; int mid = 2 + n/r; int b = 2mid+1; long int t[500][500]; for(l=0; l<b; l++){ t[0][l] = (l == mid) ? 1 : 0; } for(d=0; d<m+1; d++){ for(l=0; l<b; l++){ t[d+1][l] = 0; for(c=-8; c<9; c++){ c4l = c + 4(l-mid) + mid; t[d+1][l] += (c4l >= 0 && c4l <= 2*mid) ? t[d][c4l]*w(c) : 0; } } } printf("%ld",t[8][mid]); }