Maths Olympiad Prep

Library / /15 of 34

Algebra Difficulty 6.5 National Olympiad Prove it United States

Suppose PP is a polynomial with integer coefficients such that for every positive integer nn, the sum of the decimal digits of P(n)|P(n)| is not a Fibonacci number. Must PP be constant?
(A Fibonacci number is an element of the sequence F0,F1,F_0, F_1, \dots defined recursively by F0=0F_0 = 0, F1=1F_1 = 1, and Fk+2=Fk+1+FkF_{k+2} = F_{k+1} + F_k for k0k \ge 0.)

Solution

The answer is yes, PP must be constant. By S(n)S(n) we mean the sum of the decimal digits of n|n|.
We need two claims.

Claim — If P(x)Z[x]P(x) \in \mathbb{Z}[x] is nonconstant with positive leading coefficient, then there exists an integer polynomial F(x)F(x) such that all coefficients of PFP \circ F are positive except for the second one, which is negative.
Proof. We will actually construct a cubic FF. We call a polynomial good if it has the property.
First, consider T0(x)=x3+x+1T_0(x) = x^3 + x + 1. Observe that in T0deg PT_0^{\text{deg } P}, every coefficient is strictly positive, except for the second one, which is zero.
Then, let T1(x)=x31Dx2+x+1T_1(x) = x^3 - \frac{1}{D}x^2 + x + 1. Using continuity as DD \to \infty, it follows that if DD is large enough (in terms of deg P\text{deg } P), then T1deg PT_1^{\text{deg } P} is good, with 3Dx3deg f1-\frac{3}{D}x^{3\text{deg } f-1} being the only negative coefficient.
Finally, we can let F(x)=CT1(x)F(x) = CT_1(x) where CC is a sufficiently large multiple of DD (in terms of the coefficients of PP); thus the coefficients of (CT1(x))deg P(CT_1(x))^{\text{deg } P} dominate (and are integers), as needed. \square

Claim — There are infinitely many Fibonacci numbers in each residue class modulo 9.
Proof. Easy. First note the Fibonacci sequence is periodic modulo 9 (indeed it is periodic modulo any integer). Moreover (allowing negative indices),
F0=00(mod9)F1=11(mod9)F3=22(mod9)F4=33(mod9)F7=134(mod9)F5=55(mod9)F4=36(mod9)F9=347(mod9)F6=88(mod9). \begin{align*} F_0 &= 0 \equiv 0 \pmod{9} \\ F_1 &= 1 \equiv 1 \pmod{9} \\ F_3 &= 2 \equiv 2 \pmod{9} \\ F_4 &= 3 \equiv 3 \pmod{9} \\ F_7 &= 13 \equiv 4 \pmod{9} \\ F_5 &= 5 \equiv 5 \pmod{9} \\ F_{-4} &= -3 \equiv 6 \pmod{9} \\ F_9 &= 34 \equiv 7 \pmod{9} \\ F_6 &= 8 \equiv 8 \pmod{9}. \end{align*} \square

We now show how to solve the problem with the two claims. WLOG PP satisfies the conditions of the first claim, and choose FF as above. Let
P(F(x))=cNxNcN1xN1+cN2xN2++c0 P(F(x)) = c_N x^N - c_{N-1} x^{N-1} + c_{N-2} x^{N-2} + \dots + c_0
where ci>0c_i > 0 (and N=3deg PN = 3 \text{deg } P). Then if we select x=10ex = 10^e for ee large enough (say x>10maxicix > 10 \max_i c_i), the decimal representation P(F(10e))P(F(10^e)) consists of the concatenation of
* the decimal representation of cN1c_N - 1,
* the decimal representation of 10ecN110^e - c_{N-1}
* the decimal representation of cN2c_{N-2}, with several leading zeros,
* the decimal representation of cN3c_{N-3}, with several leading zeros,
* ...
* the decimal representation of c0c_0, with several leading zeros.
(For example, if P(F(x))=15x37x2+4x+19P(F(x)) = 15x^3 - 7x^2 + 4x + 19, then P(F(1000))=14,993,004,019P(F(1000)) = 14,993,004,019.)
Thus, the sum of the digits of this expression is equal to
S(P(F(10e)))=9e+k S(P(F(10^e))) = 9e + k
for some constant kk depending only on PP and FF, independent of ee. But this will eventually
hit a Fibonacci number by the second claim, contradiction.

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.