Maths Olympiad Prep

Library / /17 of 48

Algebra Difficulty 5.2 AIME, harder Prove it Hong Kong

Find all polynomials ff such that ff has nonnegative integer coefficients, f(1)=7f(1) = 7 and f(2)=2017f(2) = 2017.

Solution

The only polynomial is x10+x9+x8+x7+x6+x5+1x^{10} + x^9 + x^8 + x^7 + x^6 + x^5 + 1.

Suppose one of the coefficients of f0(x)=f(x)f_0(x) = f(x), say the coefficient of xkx^k, is at least 22. Define f1(x)=f0(x)2xk+xk+1f_1(x) = f_0(x) - 2x^k + x^{k+1}. Then f1(2)=f0(2)=2017f_1(2) = f_0(2) = 2017 and f1(1)<f0(1)=7f_1(1) < f_0(1) = 7. Also, the coefficients of f1f_1 are nonnegative integers. Repeating the same process, since the sequence f0(1),f1(1),f_0(1), f_1(1), \dots of nonnegative integers is strictly decreasing, the process must end at some step. Then we obtain a polynomial g(x)g(x) with coefficients 00 or 11 such that g(2)=2017g(2) = 2017 and g(1)7g(1) \le 7.

Since the binary representation of 20172017 is 1111100001(2)1111100001_{(2)}, we know that gg is uniquely determined, and is given by
g(x)=x10+x9+x8+x7+x6+x5+1. g(x) = x^{10} + x^9 + x^8 + x^7 + x^6 + x^5 + 1.
As g(1)=7g(1) = 7, the equality of g(1)7g(1) \le 7 should hold. This means we do not need to carry out any process, and ff must be the same as gg.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.