HMMT 二月 2019 · 团队赛 · 第 9 题
HMMT February 2019 — Team Round — Problem 9
题目详情
英文原题
- [ 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
解析
英文解析
- [ 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 .