返回题库

HMMT 二月 2019 · 团队赛 · 第 9 题

HMMT February 2019 — Team Round — Problem 9

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

题目详情

英文原题

  1. [ 55 ] Let p > 2 be a prime number. F [ x ] is defined as the set of all polynomials in x with coefficientspin F (the integers modulo p with usual addition and subtraction), so that two polynomials are equalpif and only if the coefficients of x are equal in F for each nonnegative integer k . For example,kp
    ( x + 2)(2 x + 3) = 2 x + 2 x + 1 in F [ x ] because the corresponding coefficients are equal modulo 5.2
    Let f, g ∈ F [ x ]. The pair ( f, g ) is called compositional if 5
    2 ppf ( g ( x )) ≡ x − xin F [ x ]. Find, with proof, the number of compositional pairs (in terms of p ). p
解析

英文解析

  1. [ 55 ] Let p > 2 be a prime number. F [ x ] is defined as the set of all polynomials in x with coefficientspin F (the integers modulo p with usual addition and subtraction), so that two polynomials are equalpif and only if the coefficients of x are equal in F for each nonnegative integer k . For example,kp
    ( x + 2)(2 x + 3) = 2 x + 2 x + 1 in F [ x ] because the corresponding coefficients are equal modulo 5.2
    Let f, g ∈ F [ x ]. The pair ( f, g ) is called compositional if 5
    2 ppf ( g ( x )) ≡ x − xin F [ x ]. Find, with proof, the number of compositional pairs (in terms of p ).
    Proposed by: Ashwin Sahp
    Answer: 4 p ( p − 1)
    Solution 1. First, notice that (deg f )(deg g ) = p and both polynomials are clearly nonconstant.2
    2 2
    Therefore there are three possibilities for the ordered pair (deg f, deg g ), which are (1 , p ) , ( p , 1), and
    ( p, p ).
    In the subsequent parts of the solution, equalities are modulo p . If f ( x ) = ax + b, a 6 = 0 is linear,
    p 2
    x − x − b − 1
    then it is invertible so then g is uniquely determined as g ( x ) = f ( f ( g ( x ))) = . Similarly,
    − 1 aif g ( x ) = cx + d, c 6 = 0 (mod p ) is linear then f is uniquely determined as f ( x ) = f ( g ( g ( x ))) =
    ( ) ( )2
    x − d x − dp − . In each case there are p ( p − 1) compositional pairs.
    c c
    The last case is deg f = deg g = p . We take the derivative of both sides (we use the formal derivative
    ∑
    n − 1
    D f ( x ) = nf x , which satisfies the usual chain and product rules but can be used onx nn ≥ 1
    arbitrary polynomials, including those in F [ x ]).
    Thusp
    ′ ′ 2 p − 12
    f ( g ( x )) g ( x ) = p x − 1 = − 1 ,
    ′ ′
    using that p = 0 in F . Now g ( x ) and f ( g ( x )) must both be constant polynomials. Since g isp
    ′
    nonconstant, this means that f ( x ) is also a constant polynomial. We must be careful here, as unlikein R , nonlinear polynomials can have constant derivatives. From the formula of derivative, we see that
    ′ p 2 ph ( x ) = 0 as a polynomial exactly when h ( x ) is a linear combination of 1 , x , x , . . . (remember that
    ′ ′
    p = 0). Thus f , g both being constant and f, g being of degree p tells usp pf ( x ) = ax + bx + c, g ( x ) = dx + ex + fwhere a, b, c, d, e, f are some elements of F . Now we must have
    2 pp p p pa ( dx + ex + f ) + b ( dx + ex + f ) + c = x − xp p pover F [ x ]. We use the fact that ( x + y ) = x + y as polynomials in F , since the binomial coefficientsp p
    ( )
    p p p pp
    ≡ 0 (mod p ) for 1 ≤ j ≤ p − 1. This implies ( x + y + z ) = x + y + z . Therefore we can expandjthe previous equation as
    2 2
    p p p p p p pa ( d x + e x + f ) + b ( dx + ex + f ) + c = x − x.
    Equating coefficients, we see thatpad = 1 ,
    ae + bd = 0 ,pbe = − 1 ,
    af + bf + c = 0 .p − p − 1
    The first and third equations imply that a, d, b, e are nonzero (mod p ) and a = d , b = − e . Thenpae + bd = 0 gives − p p − 1
    d e − e d = 0
    p +1 p +1 p − 1 p − 1 2 2
    or e = d . Recalling that e = d = 1 in (mod p ), this tells us d = e so d = ± e .
    Furthermore, any choice of such ( d, e ) give unique ( a, b ) which satisfy the first three equations. Finally,
    once we have determined a, b, d, e , any choice of f gives a unique valid choice of c .
    Thus we have p − 1 choices for d , two choices for e after choosing d (n.b. for p = 2 there is only onechoice for e , so the assumption p > 2 is used here), and then p choices for f , for a total of 2 p ( p − 1)
    compositional pairs in this case.
    Finally, adding the number of compositional pairs from all three cases, we obtain 4 p ( p − 1) compositionalpairs in total.
    Solution 2. The key step is obtainingp pf ( x ) = ax + bx + c, g ( x ) = dx + ex + fin the case where deg f = deg g = p . We present an alternative method of obtaining this, with the restof the solution being the same as the first solution. Letp p − 1
    f ( x ) = f x + f x + · · · + fp p − 1 0
    p p − 1
    g ( x ) = g x + g x + · · · + gp p − 1 0
    p pwhere f , g are nonzero. Like before, we have g ( x ) = g ( x ) in F [ x ], sop p pp p p − 12
    x − x = f g ( x ) + f g ( x ) + · · · + f .
    p p − 1 0
    Consider the maximal k < p for which f 6 = 0. (It is not hard to see that in fact k ≥ 1, as f g ( x ) + fpk p 0
    p kp − 12
    cannot be x − x .) First assume that k > 1. We look at the x coefficient, which is affected onlyk k − 1
    by the f g ( x ) term. By expanding, the coefficient is kf g g . Therefore g = 0. Then we lookk k p − 1 p − 1
    kp − 2 kp − 3 kp − p +1 pat the x coefficient, then the x coefficient, etc. down to the x coefficient to concludethat g = g = · · · = g = 0. However, then the x coefficient of f ( g ( x )) is zero, contradiction.
    p − 1 p − 2 1
    Therefore we must have k = 1, so f is of the form ax + bx + c . Using the same method as we usedpkp − p +1
    when k > 1, we get g = g = · · · g = 0, though the x coefficient is now the x coefficientp − 1 p − 2 2
    which we want to be nonzero. Hence we do not obtain g = 0 anymore and we find that g is of thep 1
    form dx + ex + f .