Maths Olympiad Prep

Library / /95 of 155

Algebra Difficulty 6.3 National olympiad Prove it Saudi Arabia

For any positive integer kk, denote the sum of digits of kk in its decimal representation by S(k)S(k). Find all polynomials P(x)P(x) with integer coefficients such that for any positive integer n2017n \geq 2017, the integer P(n)P(n) is positive and S(P(n))=P(S(n))S(P(n)) = P(S(n)).

Solution

We consider the degree of polynomial PP:

Case 1: If degP=0\deg P = 0 then P(x)cP(x) \equiv c for some cZc \in \mathbb{Z}, the given condition becomes S(c)=cS(c) = c which holds if and only if 1c91 \leq c \leq 9.

Case 2: If degP=1\deg P = 1. We notice that S(m+n)S(m)+S(n)S(m+n) \leq S(m) + S(n) for all positive integers m,nm, n and the equality occurs when there is no carry in the addition m+nm+n. Let P(x)=ax+bP(x) = a x + b for a,bZa, b \in \mathbb{Z} and a0a \neq 0. Since S(P(n))=P(S(n))S(P(n)) = P(S(n)) for n2017n \geq 2017 then aa must be positive. The given condition becomes S(an+b)=aS(n)+bS(an + b) = a S(n) + b for n2017n \geq 2017. Putting n=2025n = 2025 and n=2020n = 2020, we get
S(2025a+b)S(2020a+b)=(aS(2025)+b)(aS(2020)+b)=5a. S(2025 a + b) - S(2020 a + b) = (a S(2025) + b) - (a S(2020) + b) = 5a.
We also have
S(2025a+b)=S((2020a+b)+5a)S(2020a+b)+S(5a). S(2025 a + b) = S((2020 a + b) + 5a) \leq S(2020 a + b) + S(5a).
These imply that S(5a)5aS(5a) \geq 5a, as a1a \geq 1, this holds only when a=1a = 1. Then we have S(n+1+b)S(n+b)=S(n+1)S(n)S(n + 1 + b) - S(n + b) = S(n + 1) - S(n).

1. If b>0b > 0 then choose nn such that n+1+b=10kn + 1 + b = 10^k for some kk big enough then all digits of n+bn + b are 99 then the left hand side is 19k1 - 9k. Also note that nn is a positive integer less than 10k110^k - 1, then S(n)<9kS(n) < 9k, which means S(n+1)S(n)1(9k1)=29k>19kS(n + 1) - S(n) \geq 1 - (9k - 1) = 2 - 9k > 1 - 9k, a contradiction.

2. If b<0b < 0, similarly, we also come to a contradiction.

Thus b=0b = 0 and P(x)=xP(x) = x, which is trivially satisfied.

Case 3: If degP=d2\deg P = d \geq 2 then the leading term of PP is adnda_d n^d with ad0a_d \neq 0, then similarly we have ad>0a_d > 0. Choose n=10k1n = 10^k - 1 for some kZ+k \in \mathbb{Z}^+ big enough, then S(P(n))=P(9k)S(P(n)) = P(9k).

Since P(9k)P(9k) grows approximately as (9k)d(9k)^d while S(P(n))S(P(n)) grows approximately as a constant multiple of kk, the given equality cannot hold for sufficiently large kk since d2d \geq 2.

In conclusion, P(x)=cP(x) = c for some c{1,2,3,,9}c \in \{1,2,3, \ldots, 9\} or P(x)=xP(x) = x, x\forall x. \square

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 and solution reproduced as published; topic and difficulty added by this site.