PUMaC 2021 · 数论（A 组） · 第 7 题
PUMaC 2021 — Number Theory (Division A) — Problem 7
题目详情
- We say that a polynomial p is respectful if ∀ x, y ∈ Z , y − x divides p ( y ) − p ( x ) , and ∀ x ∈ Z , p ( x ) ∈ Z . We say that a respectful polynomial is disguising if it is nonzero, and all of its P non-zero coefficients lie between 0 and 1 , exclusive. Determine deg ( f ) · f (2), where the sum includes all disguising polynomials f of degree at most 5 . a i − 1
解析
- We say that a polynomial p is respectful if ∀ x, y ∈ Z , y − x divides p ( y ) − p ( x ) , and ∀ x ∈ Z , p ( x ) ∈ Z . We say that a respectful polynomial is disguising if it is nonzero, and all of P its non-zero coefficients lie between 0 and 1 , exclusive. Determine deg ( f ) · f (2) over all disguising polynomials f of degree at most 5 . Proposed by: Frank Lu Answer: 290 First, we claim that all respectful polynomials of degree 3 or less have integer coefficients. To see this, note that f (0) = 0 . Consider now f (1) , f (2) , f (3) . By Lagrange Interpolation, this polynomial is uniquely determined by these values. Note that we can write this polynomial as f (3) f (2) f (1) x ( x − 1)( x − 2) − x ( x − 1)( x − 3)+ x ( x − 2)( x − 3) , by the above properties. Note that 6 2 2 the second term is a polynomial with integer coefficients. However, note that f (3) is divisible by 3 , and is a multiple of 2 different from f (1) . Hence, note that f (3) / 3 and f (1) are both integers of the same parity. Note then that this will result in an integer-coefficient polynomial, proving the desired. In particular, no disguising polynomials of degree 3 or lower exist. We now consider the case for degree at most 5 in general. For simplicity, let a ( x ) = x ( x − 1)( x − 2) · · · ( x − 5) . P 5 a ( x ) 5 − i 1 Again, we can write the polynomial in the above form, as ( − 1) . Now, i =1 i !(5 − i )! x − i note that f (5) ≡ f (2) (mod 3) , which also means that f (5) ≡ 10 f (2) (mod 3) . Similarly, we have that f (4) ≡ f (1) (mod 3) . We can thus write this expression as x ( x − 1)( x − 3)( x − f (5) − 10 f (2) 5 f (5) − 20 f (2) f (4) − f (1) 4 f (4) − f (1) f (3) 4)( x − )+ x ( x − 2)( x − 3)( x − 5)( x − )+ x ( x − 1)( x − 120 120 24 24 6 2)( x − 4)( x − 5) . This shows us that the denominators of the coefficients have to divide 8; indeed, note that f (5) − 10 f (2) and 5 f (5) − 20 f (2) are both divisible by 15 . Furthermore, we could alternatively re-write this by taking (mod 2) . This instead yields the expression (splitting the f (1)+ f (3) f (1)+3 f (3) term corresponding to i = 3 in half) x ( x − 2)( x − 4)( x − 5)( x + )+ x ( x − 1)( x − 24 24 5 f (3)+ f (5) 15 f (3)+5 f (5) 2)( x − 4)( x + ) + . . . , with the remaining terms having leading coefficients 120 120 f (2) f (4) and , which have denominators that are not divisible by 4 . This further shows that 12 24 the denominators have to divide 4 . Repeating this argument for 4th degree polynomials shows that all the denominators, in fact, have to divide 2 , by only noticing the leading coefficients of the terms with f (4) , f (1) . Checking the case for 4 , notice that there can only be one such disguising polynomial; if there were two, since both of the leading coefficients are the same, it follows that their difference is somewhat disguising. But this doesn’t exist for a polynomial 4 2 x + x of degree at most 3 . Thus, noticing that is disguising, we see that this the only one for 2 this degree. By a similar token, notice that for any two disguising polynomials of degree 5 that have the same leading coefficient, notice that f − g must be an integer polynomial away 4 2 x + x from . But the largest difference between the coefficients is − 1 . This means that either 2 4 2 x + x such polynomials are equal or differ by , so there are at most 6 of these, with at most 2 5 3 1 x + x 2 for a given leading coefficient. For leading coefficient, we see that is disguising; 2 2 ( x − y ) 4 3 2 2 3 4 2 2 the difference we have for x, y is ( x + x y + x y + xy + y + x + xy + y ) . But 2 notice that this is equivalent to 2 x + 2 y + 4 xy (mod 2) since all powers of any integer have 5 4 3 2 x + x + x + x the same parity. Thus, we see that is also disguising. For the coefficient with 2 1 , for this to be an integer at all, this has to double to some of the disguising polynomial, 4 5 3 4 2 x + x 1 i x + x meaning that this is , possibly with some x terms. By the difference with , 4 2 2 we only need to consider 8 of these. Trying these out, note that only 4 of them actually 5 4 3 5 3 5 3 5 4 3 x +2 x + x x +3 x x + x +2 x x +2 x +3 x +2 x yield integers: , , , and . Requiring that f (4) is also 4 4 4 4 divisible by 4 restricts us to the first two possibilities. The second breaks down: plugging 3 5 · 28 in x = 5 yields = 7 · 125 , which is not equivalent to 1 (mod 4) . As for the first, note 4 3 16 that f (3) = 27 = 27 · 4 = 108 , which isn’t equivalent to 1 (mod 4) . This means that no 4 4 2 5 3 x + x x + x other disguising polynomials exist. Our three disguising polynomials are thus , , 2 2 5 4 3 2 x + x + x + x and , which take on values 10 , 20 , and 30 , resulting that 10 · 4 + (20 + 30) · 5 = 290 . 2 a i − 1