HMMT 二月 2020 · ALGNT 赛 · 第 6 题

6. A polynomial P ( x ) is a base- n polynomial if it is of the form a x + a x + · · · + a x + a , where d d − 1 1 0 each a is an integer between 0 and n − 1 inclusive and a > 0. Find the largest positive integer n such i d √ √ that for any real number c , there exists at most one base- n polynomial P ( x ) for which P ( 2+ 3) = c . Proposed by: James Lin Answer: 9 Solution: It is equivalent to determine the largest n such that we cannot find two distinct base- √ √ √ √ n polynomials P and P such that P ( 2 + 3) = P ( 2 + 3). The difference of two base- n 1 2 1 2 polynomials is a polynomial with integer coefficients whose absolute values are less than n , and all such polynomials are the difference of two base- n polynomials. We compute the minimal polynomial √ √ √ 2 2 2 4 2 of x = 2 + 3 first: since x = 5 + 2 6, we have ( x − 5) = 24 so x − 10 x + 1 = 0. Therefore √ √ 2 4 2 6 4 2 2 + 3 is a root of ( x + 1)( x − 10 x + 1) = x − 9 x − 9 x + 1. The coefficients of this polynomial have magnitude at most 9, so n < 10. √ √ √ k In the other direction, observe that ( 2 + 3) is of the form a + b 6 for integers a and b if k is √ √ even, and a 2 + b 3 if k is odd. As no integer linear combination of the first expression can equal the 2 d 2 d − 2 second, we can treat these cases separately. Suppose Q ( x ) = c x + c x + · · · + c is an even d d − 1 0 √ √ √ 2 polynomial with | c | < 9 for all i and c 6 = 0. Let y = ( 2 + 3) = 5 + 2 6 and observe that y > 9. i d Then d d | c y | ≥ y d 8 d

( y − 1) y − 1 d − 1 d − 2 = 8 y + 8 y + · · · + 8 y + 8 d − 1 d − 2 ≥ | c y + c y + · · · + c | . d − 1 d − 2 0 √ √ d d − 1 Therefore Q ( 2 + 3) = c y + c y + · · · + c 6 = 0, so no two distinct base-9 polynomials coincide d d − 1 0 √ √ at x = 2 + 3. √ √ The same logic applies for the odd polynomial case after dividing out a factor of 2 + 3, so n = 9 works.