返回题库

HMMT 二月 2020 · ALGNT 赛 · 第 10 题

HMMT February 2020 — ALGNT Round — Problem 10

专题
Discrete 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 coefficients k 2 of x are equal in F for each nonnegative integer k . For example, ( x + 3)(100 x + 5) = 100 x + 2 x + 15 101 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 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 coefficients k 2 of x are equal in F for each nonnegative integer k . For example, ( x + 3)(100 x + 5) = 100 x + 2 x + 15 101 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 such that 1001 101 f ( x ) = g ( x )( x − 1) + h ( x ) − h ( x ) in F [ x ]. Find the number of lucky polynomials. 101 Proposed by: Michael Ren 954 Answer: 101 m Solution 1: Let p = 101, m = 1001, and work in the ring R := F [ x ] / ( x − 1). We want to find the p p number of elements a of this ring that are of the form x − x . We first solve this question for a field p p p extension F d of F . Note that ( x + n ) − ( x + n ) = x − x for any n ∈ F , and the polynomial t − t = b p p p p has at most p solutions in F d for any b ∈ F d . Combining these implies that t − t = b always has p p d − 1 p either p or 0 solutions in F d , so there are p elements of F d expressible in the form x − x . Now, p p note that we may factor R into a product of field extensions of F , each corresponding to an irreducible p m m factor of x − 1 in F , as the polynomial x − 1 has no double roots in F as p - m . By the Chinese p p Remainder Theorem, we may multiply the number of lucky polynomials for each of the field extensions d − 1 to find the final answer. A field extension of degree d will yield p lucky polynomials. Thus, the m − q final answer is p , where q is the number of fields in the factorization of R into fields. To do determine q , we first factor ∏ m x − 1 = Φ ( x ) k k | m in Z [ x ] where Φ ( x ) are the cyclotomic polynomials. Then we compute the number of irreducible k ϕ ( k ) divisors of the cyclotomic polynomial Φ ( x ) in F [ x ]. We claim that this is equal to . Indeed, k p ord ( p ) k note that given a root ω of Φ in the algebraic closure of F , the roots of its minimal polynomial are k p 2 p p ω, ω , ω , . . . , 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 irreducible k k ord ( p ) k polynomials. It remains to compute orders. We have that ord (101) = ord (3) = 6 , 7 7 ord (101) = ord (2) = 10 , 11 11 ord (101) = ord (10) = 6 . 13 13 Thus, ord (101) = 30 , 77 ord (101) = 6 , 91 ord (101) = 30 , 143 ord (101) = 30 , 1001 ord (101) = 1 . 1 1001 The number of factors of x − 1 in F [ x ] is thus 101 1 6 10 12 60 72 120 720
              • = 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 . m Solution 2: As in the previous solution, we work in the ring R = F / ( x − 1), which we can treat as p the set of polynomials in F [ x ] with degree less than m . The problem is asking us for the number of p p p p p elements of the map α : h 7 → h − h in R . Note that this map is linear because ( a + b ) = a + b in any field where p = 0 (which R is an example of). Hence it suffices to determine the size of the kernel of α . We can directly compute that if m − 1 m − 2 h ( x ) = a x + a x + · · · + a x + a , m − 1 m − 2 1 0 then p p ( m − 1) p ( m − 2) p h ( 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 k k pk where indices are taken modulo m . Letting q denote the number of orbits of the map x 7 → px in Z /m Z , q m − q the size of the kernel is then p so the size of the image is p . It remains to compute q , which will end up being the same computation as in the previous solution.