Maths Olympiad Prep

Library / /92 of 144

Number theory Difficulty 8.4 Shortlist Find the answer

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 n2016n \geq 2016, the integer P(n)P(n) is positive and S(P(n))=P(S(n)).S(P(n)) = P(S(n)).

[i]

A number or a short expression. Spacing and $ signs are ignored.

Solution

We are asked to find all polynomials P(x) P(x) with integer coefficients such that for any positive integer n2016 n \geq 2016 , the following condition holds:
S(P(n))=P(S(n)), S(P(n)) = P(S(n)),
where S(k) S(k) denotes the sum of the digits of the integer k k .

### Step 1: Analyzing the Condition

Firstly, we observe the property:
S(P(n))=P(S(n)). S(P(n)) = P(S(n)).
This condition suggests a relationship between the polynomial evaluated at a number n n and evaluated at the sum of its digits.

### Step 2: Testing Simple Polynomials

A natural starting point is to check simple polynomials, such as constant polynomials and linear polynomials.

#### Case 1: Constant Polynomial P(x)=c P(x) = c

If P(x)=c P(x) = c , then:
- S(P(n))=S(c)=c S(P(n)) = S(c) = c (since c{1,2,,9} c \in \{1, 2, \ldots, 9\} for S(c)=c S(c) = c ).
- P(S(n))=c P(S(n)) = c .

In this case, if c c is a single-digit integer (1 to 9), both sides of the equation match, i.e., S(P(n))=P(S(n)) S(P(n)) = P(S(n)) . Therefore, polynomials of the form P(x)=c P(x) = c where c{1,,9} c \in \{1, \ldots, 9\} satisfy the condition.

#### Case 2: Linear Polynomial P(x)=x P(x) = x

Consider P(x)=x P(x) = x :
- S(P(n))=S(n) S(P(n)) = S(n) .
- P(S(n))=S(n) P(S(n)) = S(n) .

Clearly, the equation holds as S(n)=S(n) S(n) = S(n) . Therefore, P(x)=x P(x) = x satisfies the condition.

### Step 3: Excluding Higher-Degree Polynomials

For a polynomial of degree 2 or higher such as P(x)=ax2+bx+c P(x) = ax^2 + bx + c :
- The value P(n) P(n) grows as n2 n^2 , which means S(P(n)) S(P(n)) could significantly differ from a simple expression like P(S(n)) P(S(n)) in terms of complexity and digit count.
- It is unlikely that S(P(n))=P(S(n)) S(P(n)) = P(S(n)) can hold universally for all n2016 n \geq 2016 due to this disparity in growth rates and digit sums unless P(x)=x P(x) = x .

### Conclusion

The polynomials satisfying the given condition are constants within the range where their digit sum equals themselves and the identity polynomial, specifically:
P(x)=c,c{1,,9} P(x) = c, \quad c \in \{1, \ldots, 9\}
and
P(x)=x. P(x) = x.

Thus, the set of all such polynomials is:
P(x)=c(c{1,,9})andP(x)=x. \boxed{P(x) = c \quad (c \in \{1, \ldots, 9\}) \quad \text{and} \quad P(x) = x}.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.