返回题库

HMMT 二月 2020 · ALGNT 赛 · 第 10 题

HMMT February 2020 — ALGNT Round — Problem 10

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

题目详情

英文原题

  1. We define F [ x ] as the set of all polynomials in x with coefficients in F (the integers modulo 101
    101 101
    with usual addition and subtraction), so that two polynomials are equal if and only if the coefficientsk 2
    of x are equal in F for each nonnegative integer k . For example, ( x + 3)(100 x + 5) = 100 x + 2 x + 15
    in F [ x ] because the corresponding coefficients are equal modulo 101.101
    We say that f ( x ) ∈ F [ x ] is lucky if it has degree at most 1000 and there exist g ( x ) , h ( x ) ∈ F [ x ]101
    101 101
    such that
    1001 101
    f ( x ) = g ( x )( x − 1) + h ( x ) − h ( x )
    in F [ x ]. Find the number of lucky polynomials.
    101
解析

英文解析

  1. We define F [ x ] as the set of all polynomials in x with coefficients in F (the integers modulo 101
    101 101
    with usual addition and subtraction), so that two polynomials are equal if and only if the coefficientsk 2
    of x are equal in F for each nonnegative integer k . For example, ( x + 3)(100 x + 5) = 100 x + 2 x + 15
    in F [ x ] because the corresponding coefficients are equal modulo 101.101
    We say that f ( x ) ∈ F [ x ] is lucky if it has degree at most 1000 and there exist g ( x ) , h ( x ) ∈ F [ x ]101
    101 101
    such that
    1001 101
    f ( x ) = g ( x )( x − 1) + h ( x ) − h ( x )
    in F [ x ]. Find the number of lucky polynomials.
    Proposed by: Michael Ren 101
    Answer: 101954
    Solution 1: Let p = 101, m = 1001, and work in the ring R := F [ x ] / ( x − 1). We want to find thempnumber of elements a of this ring that are of the form x − x . We first solve this question for a fieldpp p pextension F d of F . Note that ( x + n ) − ( x + n ) = x − x for any n ∈ F , and the polynomial t − t = bp phas at most p solutions in F d for any b ∈ F d . Combining these implies that t − t = b always hasppp pd − 1 peither p or 0 solutions in F d , so there are p elements of F d expressible in the form x − x . Now,
    p pnote that we may factor R into a product of field extensions of F , each corresponding to an irreduciblem mpfactor of x − 1 in F , as the polynomial x − 1 has no double roots in F as p - m . By the Chinesep p
    Remainder Theorem, we may multiply the number of lucky polynomials for each of the field extensionsd − 1
    to find the final answer. A field extension of degree d will yield p lucky polynomials. Thus, them − qfinal answer is p , where q is the number of fields in the factorization of R into fields.
    To do determine q , we first factor
    ∏
    x − 1 = Φ ( x )mkk | min Z [ x ] where Φ ( x ) are the cyclotomic polynomials. Then we compute the number of irreducibleϕ ( k )kdivisors of the cyclotomic polynomial Φ ( x ) in F [ x ]. We claim that this is equal to . Indeed,
    k pord ( p )
    note that given a root ω of Φ in the algebraic closure of F , the roots of its minimal polynomial arekk pp p 2
    ω, ω , ω , . . . , and this will cycle after the numerator repeats modulo k , from which it follows that ϕ ( k )
    the degree of the minimal polynomial of ω is ord ( p ). Thus, Φ ( x ) factors into irreduciblek kord ( p )
    polynomials.k
    It remains to compute orders. We have thatord (101) = ord (3) = 6 ,
    7 7
    ord (101) = ord (2) = 10 ,
    11 11
    ord (101) = ord (10) = 6 .
    13 13
    Thus,
    ord (101) = 30 ,
    ord (101) = 6 ,77
    ord (101) = 30 ,91
    ord (101) = 30 ,143
    1001
    ord (101) = 1 .
    10011
    The number of factors of x − 1 in F [ x ] is thus
    1 6 10 12 60 72 120 720101 + + + + + + + = 1 + 1 + 1 + 2 + 2 + 12 + 4 + 24 = 47 ,
    1 6 10 6 30 6 30 30
    1001 − 47 954
    so the total number of lucky polynomials is 101 = 101 .
    Solution 2: As in the previous solution, we work in the ring R = F / ( x − 1), which we can treat asmpthe set of polynomials in F [ x ] with degree less than m . The problem is asking us for the number ofpp p p pelements of the map α : h 7 → h − h in R . Note that this map is linear because ( a + b ) = a + b inany field where p = 0 (which R is an example of). Hence it suffices to determine the size of the kernelof α .
    We can directly compute that ifm − 1 m − 2
    h ( x ) = a x + a x + · · · + a x + a ,
    m − 1 m − 2 1 0
    thenp p ( m − 1) p ( m − 2) ph ( x ) = a x + a x + · · · + a x + a ,
    m − 1 m − 2 1 0
    where exponents are taken modulo m . Therefore h is in the kernel if and only if a = a for all kk pkwhere indices are taken modulo m . Letting q denote the number of orbits of the map x 7 → px in Z /m Z ,
    q m − qthe size of the kernel is then p so the size of the image is p . It remains to compute q , which willend up being the same computation as in the previous solution.