返回题库

HMMT 十一月 2019 · 冲刺赛 · 第 34 题

HMMT November 2019 — Guts Round — Problem 34

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

题目详情

英文原题

  1. [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 .
    ⌊ ⌋
    ( )
    N E4
    An estimate of E will earn 20 min , points.
    E N
解析

英文解析

  1. [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 .
    ⌊ ⌋
    ( )
    N E4
    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
    ( c x + . . . + c x + c )( x − 4) .6
    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 waysk k +1 kof choosing c . Therefore if we pick c , . . . , c in this order, there should be around (15 / 4) tricky 7
    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 ipolynomials.
    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
    ∑
    integer n can be written in the form ε 4 in at most one way. Therefore the number of nearly trickykk
    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 ofdegree at most i of the formd − 1 d − 2 d − 1 (x + c x + · · · + c )( x − 4) + ( ε x + · · · + ε x + ε ) .
    d − 2 0 d − 1 1 0
    which has integer coefficients between − 7 and 7 except the leading term x . It follows that t (0 , 0) =d 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 ared − 1
    t ( d, c ) ways to pick c , . . . , c , ε , . . . , ε , and exactly w ( c − 4 ` ) ways of picking ε , whered − 1 d − 2 0 d − 1 0 d − 1 dw ( k ) = min(9 − | k | , 3) for | k | ≤ 8 and 0 otherwise. Therefore setting c = c − 4 ` we haved − 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,c 4 l;
    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++){
    c 4 l = c + 4
    (l-mid) + mid;
    t[d+1][l] += (c 4 l >= 0 && c 4 l <= 2*mid) ? t[d][c 4 l]*w(c) : 0;
    }
    }
    }
    printf("%ld",t[8][mid]);
    }