Stay ahead of learning milestones! Enroll in a class over the summer!

G
Topic
First Poster
Last Poster
k a May Highlights and 2025 AoPS Online Class Information
jlacosta   0
Thursday at 11:16 PM
May is an exciting month! National MATHCOUNTS is the second week of May in Washington D.C. and our Founder, Richard Rusczyk will be presenting a seminar, Preparing Strong Math Students for College and Careers, on May 11th.

Are you interested in working towards MATHCOUNTS and don’t know where to start? We have you covered! If you have taken Prealgebra, then you are ready for MATHCOUNTS/AMC 8 Basics. Already aiming for State or National MATHCOUNTS and harder AMC 8 problems? Then our MATHCOUNTS/AMC 8 Advanced course is for you.

Summer camps are starting next month at the Virtual Campus in math and language arts that are 2 - to 4 - weeks in duration. Spaces are still available - don’t miss your chance to have an enriching summer experience. There are middle and high school competition math camps as well as Math Beasts camps that review key topics coupled with fun explorations covering areas such as graph theory (Math Beasts Camp 6), cryptography (Math Beasts Camp 7-8), and topology (Math Beasts Camp 8-9)!

Be sure to mark your calendars for the following upcoming events:
[list][*]May 9th, 4:30pm PT/7:30pm ET, Casework 2: Overwhelming Evidence — A Text Adventure, a game where participants will work together to navigate the map, solve puzzles, and win! All are welcome.
[*]May 19th, 4:30pm PT/7:30pm ET, What's Next After Beast Academy?, designed for students finishing Beast Academy and ready for Prealgebra 1.
[*]May 20th, 4:00pm PT/7:00pm ET, Mathcamp 2025 Qualifying Quiz Part 1 Math Jam, Problems 1 to 4, join the Canada/USA Mathcamp staff for this exciting Math Jam, where they discuss solutions to Problems 1 to 4 of the 2025 Mathcamp Qualifying Quiz!
[*]May 21st, 4:00pm PT/7:00pm ET, Mathcamp 2025 Qualifying Quiz Part 2 Math Jam, Problems 5 and 6, Canada/USA Mathcamp staff will discuss solutions to Problems 5 and 6 of the 2025 Mathcamp Qualifying Quiz![/list]
Our full course list for upcoming classes is below:
All classes run 7:30pm-8:45pm ET/4:30pm - 5:45pm PT unless otherwise noted.

Introductory: Grades 5-10

Prealgebra 1 Self-Paced

Prealgebra 1
Tuesday, May 13 - Aug 26
Thursday, May 29 - Sep 11
Sunday, Jun 15 - Oct 12
Monday, Jun 30 - Oct 20
Wednesday, Jul 16 - Oct 29

Prealgebra 2 Self-Paced

Prealgebra 2
Wednesday, May 7 - Aug 20
Monday, Jun 2 - Sep 22
Sunday, Jun 29 - Oct 26
Friday, Jul 25 - Nov 21

Introduction to Algebra A Self-Paced

Introduction to Algebra A
Sunday, May 11 - Sep 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Wednesday, May 14 - Aug 27
Friday, May 30 - Sep 26
Monday, Jun 2 - Sep 22
Sunday, Jun 15 - Oct 12
Thursday, Jun 26 - Oct 9
Tuesday, Jul 15 - Oct 28

Introduction to Counting & Probability Self-Paced

Introduction to Counting & Probability
Thursday, May 15 - Jul 31
Sunday, Jun 1 - Aug 24
Thursday, Jun 12 - Aug 28
Wednesday, Jul 9 - Sep 24
Sunday, Jul 27 - Oct 19

Introduction to Number Theory
Friday, May 9 - Aug 1
Wednesday, May 21 - Aug 6
Monday, Jun 9 - Aug 25
Sunday, Jun 15 - Sep 14
Tuesday, Jul 15 - Sep 30

Introduction to Algebra B Self-Paced

Introduction to Algebra B
Tuesday, May 6 - Aug 19
Wednesday, Jun 4 - Sep 17
Sunday, Jun 22 - Oct 19
Friday, Jul 18 - Nov 14

Introduction to Geometry
Sunday, May 11 - Nov 9
Tuesday, May 20 - Oct 28
Monday, Jun 16 - Dec 8
Friday, Jun 20 - Jan 9
Sunday, Jun 29 - Jan 11
Monday, Jul 14 - Jan 19

Paradoxes and Infinity
Mon, Tue, Wed, & Thurs, Jul 14 - Jul 16 (meets every day of the week!)

Intermediate: Grades 8-12

Intermediate Algebra
Sunday, Jun 1 - Nov 23
Tuesday, Jun 10 - Nov 18
Wednesday, Jun 25 - Dec 10
Sunday, Jul 13 - Jan 18
Thursday, Jul 24 - Jan 22

Intermediate Counting & Probability
Wednesday, May 21 - Sep 17
Sunday, Jun 22 - Nov 2

Intermediate Number Theory
Sunday, Jun 1 - Aug 24
Wednesday, Jun 18 - Sep 3

Precalculus
Friday, May 16 - Oct 24
Sunday, Jun 1 - Nov 9
Monday, Jun 30 - Dec 8

Advanced: Grades 9-12

Olympiad Geometry
Tuesday, Jun 10 - Aug 26

Calculus
Tuesday, May 27 - Nov 11
Wednesday, Jun 25 - Dec 17

Group Theory
Thursday, Jun 12 - Sep 11

Contest Preparation: Grades 6-12

MATHCOUNTS/AMC 8 Basics
Friday, May 23 - Aug 15
Monday, Jun 2 - Aug 18
Thursday, Jun 12 - Aug 28
Sunday, Jun 22 - Sep 21
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

MATHCOUNTS/AMC 8 Advanced
Sunday, May 11 - Aug 10
Tuesday, May 27 - Aug 12
Wednesday, Jun 11 - Aug 27
Sunday, Jun 22 - Sep 21
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

AMC 10 Problem Series
Friday, May 9 - Aug 1
Sunday, Jun 1 - Aug 24
Thursday, Jun 12 - Aug 28
Tuesday, Jun 17 - Sep 2
Sunday, Jun 22 - Sep 21 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Monday, Jun 23 - Sep 15
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

AMC 10 Final Fives
Sunday, May 11 - Jun 8
Tuesday, May 27 - Jun 17
Monday, Jun 30 - Jul 21

AMC 12 Problem Series
Tuesday, May 27 - Aug 12
Thursday, Jun 12 - Aug 28
Sunday, Jun 22 - Sep 21
Wednesday, Aug 6 - Oct 22

AMC 12 Final Fives
Sunday, May 18 - Jun 15

AIME Problem Series A
Thursday, May 22 - Jul 31

AIME Problem Series B
Sunday, Jun 22 - Sep 21

F=ma Problem Series
Wednesday, Jun 11 - Aug 27

WOOT Programs
Visit the pages linked for full schedule details for each of these programs!


MathWOOT Level 1
MathWOOT Level 2
ChemWOOT
CodeWOOT
PhysicsWOOT

Programming

Introduction to Programming with Python
Thursday, May 22 - Aug 7
Sunday, Jun 15 - Sep 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Tuesday, Jun 17 - Sep 2
Monday, Jun 30 - Sep 22

Intermediate Programming with Python
Sunday, Jun 1 - Aug 24
Monday, Jun 30 - Sep 22

USACO Bronze Problem Series
Tuesday, May 13 - Jul 29
Sunday, Jun 22 - Sep 1

Physics

Introduction to Physics
Wednesday, May 21 - Aug 6
Sunday, Jun 15 - Sep 14
Monday, Jun 23 - Sep 15

Physics 1: Mechanics
Thursday, May 22 - Oct 30
Monday, Jun 23 - Dec 15

Relativity
Mon, Tue, Wed & Thurs, Jun 23 - Jun 26 (meets every day of the week!)
0 replies
jlacosta
Thursday at 11:16 PM
0 replies
k i Adding contests to the Contest Collections
dcouchman   1
N Apr 5, 2023 by v_Enhance
Want to help AoPS remain a valuable Olympiad resource? Help us add contests to AoPS's Contest Collections.

Find instructions and a list of contests to add here: https://artofproblemsolving.com/community/c40244h1064480_contests_to_add
1 reply
dcouchman
Sep 9, 2019
v_Enhance
Apr 5, 2023
k i Zero tolerance
ZetaX   49
N May 4, 2019 by NoDealsHere
Source: Use your common sense! (enough is enough)
Some users don't want to learn, some other simply ignore advises.
But please follow the following guideline:


To make it short: ALWAYS USE YOUR COMMON SENSE IF POSTING!
If you don't have common sense, don't post.


More specifically:

For new threads:


a) Good, meaningful title:
The title has to say what the problem is about in best way possible.
If that title occured already, it's definitely bad. And contest names aren't good either.
That's in fact a requirement for being able to search old problems.

Examples:
Bad titles:
- "Hard"/"Medium"/"Easy" (if you find it so cool how hard/easy it is, tell it in the post and use a title that tells us the problem)
- "Number Theory" (hey guy, guess why this forum's named that way¿ and is it the only such problem on earth¿)
- "Fibonacci" (there are millions of Fibonacci problems out there, all posted and named the same...)
- "Chinese TST 2003" (does this say anything about the problem¿)
Good titles:
- "On divisors of a³+2b³+4c³-6abc"
- "Number of solutions to x²+y²=6z²"
- "Fibonacci numbers are never squares"


b) Use search function:
Before posting a "new" problem spend at least two, better five, minutes to look if this problem was posted before. If it was, don't repost it. If you have anything important to say on topic, post it in one of the older threads.
If the thread is locked cause of this, use search function.

Update (by Amir Hossein). The best way to search for two keywords in AoPS is to input
[code]+"first keyword" +"second keyword"[/code]
so that any post containing both strings "first word" and "second form".


c) Good problem statement:
Some recent really bad post was:
[quote]$lim_{n\to 1}^{+\infty}\frac{1}{n}-lnn$[/quote]
It contains no question and no answer.
If you do this, too, you are on the best way to get your thread deleted. Write everything clearly, define where your variables come from (and define the "natural" numbers if used). Additionally read your post at least twice before submitting. After you sent it, read it again and use the Edit-Button if necessary to correct errors.


For answers to already existing threads:


d) Of any interest and with content:
Don't post things that are more trivial than completely obvious. For example, if the question is to solve $x^{3}+y^{3}=z^{3}$, do not answer with "$x=y=z=0$ is a solution" only. Either you post any kind of proof or at least something unexpected (like "$x=1337, y=481, z=42$ is the smallest solution). Someone that does not see that $x=y=z=0$ is a solution of the above without your post is completely wrong here, this is an IMO-level forum.
Similar, posting "I have solved this problem" but not posting anything else is not welcome; it even looks that you just want to show off what a genius you are.

e) Well written and checked answers:
Like c) for new threads, check your solutions at least twice for mistakes. And after sending, read it again and use the Edit-Button if necessary to correct errors.



To repeat it: ALWAYS USE YOUR COMMON SENSE IF POSTING!


Everything definitely out of range of common sense will be locked or deleted (exept for new users having less than about 42 posts, they are newbies and need/get some time to learn).

The above rules will be applied from next monday (5. march of 2007).
Feel free to discuss on this here.
49 replies
ZetaX
Feb 27, 2007
NoDealsHere
May 4, 2019
BMO 2024 SL C1
GreekIdiot   11
N 9 minutes ago by cursed_tangent1434
Let $n$, $k$ be positive integers. Julia and Florian play a game on a $2n \times 2n$ board. Julia
has secretly tiled the entire board with invisible dominos. Florian now chooses $k$ cells.
All dominos covering at least one of these cells then turn visible. Determine the minimal
value of $k$ such that Florian has a strategy to always deduce the entire tiling.
11 replies
+1 w
GreekIdiot
Apr 27, 2025
cursed_tangent1434
9 minutes ago
Cyclic quadrilateral and a tangent
a_507_bc   6
N 15 minutes ago by User141208
Source: IMOC 2023 G6
Triangle $ABC$ has circumcenter $O$. $D$ is the foot from $A$ to $BC$, and $P$ is apoint on $AD$. The feet from $P$ to $CA, AB$ are $E, F$, respectively, and the foot from $D$ to $EF$ is $T$. $AO$ meets $(ABC)$ again at $A'$. $A'D$ meets $(ABC)$ again at $R$. If $Q$ is a point on $AO$ satisfying $\angle ABP = \angle QBC$, prove that $D, P, T, R$ lie on acircle and $DQ$ is tangent to it.
6 replies
+1 w
a_507_bc
Sep 9, 2023
User141208
15 minutes ago
Geometry
blug   0
18 minutes ago
Source: own
Let $H$ be the orthocenter of triangle $ABC$. Let $p, q$ be angle bisectors of $AHB$ and $AHC$ respectively. We denote $K=p\cap AB, L=p\cap AC, M=q\cap AC, N=q\cap AB$. Circumcircles of $NKH$ and $MHL$ intersect at $P\ne H$. Prove that
$$\angle BAC=\angle PKL+\angle PMN.$$
0 replies
blug
18 minutes ago
0 replies
Random modulos
m4thbl3nd3r   6
N 19 minutes ago by Drakkur
Find all pair of integers $(x,y)$ s.t $x^2+3=y^7$
6 replies
m4thbl3nd3r
Apr 7, 2025
Drakkur
19 minutes ago
XZ passes through the midpoint of BK, isosceles, KX = CX, angle bisector
parmenides51   5
N an hour ago by Kyj9981
Source: 1st Girls in Mathematics Tournament 2019 p5 (Brazil) / Torneio Meninas na Matematica (TM^2 )
Let $ABC$ be an isosceles triangle with $AB = AC$. Let $X$ and $K$ points over $AC$ and $AB$, respectively, such that $KX = CX$. Bisector of $\angle AKX$ intersects line $BC$ at $Z$. Show that $XZ$ passes through the midpoint of $BK$.
5 replies
parmenides51
May 25, 2020
Kyj9981
an hour ago
Solution needed ASAP
UglyScientist   7
N an hour ago by Captainscrubz
$ABC$ is acute triangle. $H$ is orthocenter, $M$ is the midpoint of $BC$, $L$ is the midpoint of smaller arc $BC$. Point $K$ is on $AH$ such that, $MK$ is perpendicular to $AL$. Prove that: $HMLK$ is paralelogram(Synthetic sol needed).
7 replies
UglyScientist
4 hours ago
Captainscrubz
an hour ago
Diophantine Equation with prime numbers and bonus conditions
p.lazarov06   10
N an hour ago by mathbetter
Source: 2023 Bulgaria JBMO TST Problem 3
Find all natural numbers $a$, $b$, $c$ and prime numbers $p$ and $q$, such that:

$\blacksquare$ $4\nmid c$
$\blacksquare$ $p\not\equiv 11\pmod{16}$
$\blacksquare$ $p^aq^b-1=(p+4)^c$
10 replies
1 viewing
p.lazarov06
May 7, 2023
mathbetter
an hour ago
Concurrence in Cyclic Quadrilateral
GrantStar   39
N an hour ago by ItsBesi
Source: IMO Shortlist 2023 G3
Let $ABCD$ be a cyclic quadrilateral with $\angle BAD < \angle ADC$. Let $M$ be the midpoint of the arc $CD$ not containing $A$. Suppose there is a point $P$ inside $ABCD$ such that $\angle ADB = \angle CPD$ and $\angle ADP = \angle PCB$.

Prove that lines $AD, PM$, and $BC$ are concurrent.
39 replies
GrantStar
Jul 17, 2024
ItsBesi
an hour ago
IMO Genre Predictions
ohiorizzler1434   22
N an hour ago by rhydon516
Everybody, with IMO upcoming, what are you predictions for the problem genres?


Personally I predict: predict
22 replies
ohiorizzler1434
Today at 6:51 AM
rhydon516
an hour ago
Inequality
MathsII-enjoy   1
N 2 hours ago by arqady
A interesting problem generalized :-D
1 reply
MathsII-enjoy
3 hours ago
arqady
2 hours ago
Inequality
lgx57   2
N 2 hours ago by mashumaro
Source: Own
$a,b,c>0,ab+bc+ca=1$. Prove that

$$\sum \sqrt{8ab+1} \ge 5$$
(I don't know whether the equality holds)
2 replies
lgx57
2 hours ago
mashumaro
2 hours ago
Find min
lgx57   1
N 2 hours ago by arqady
Source: Own
Find min of $\dfrac{a^2}{ab+1}+\dfrac{b^2+2}{a+b}$
1 reply
lgx57
2 hours ago
arqady
2 hours ago
Product is a perfect square( very easy)
Nuran2010   1
N 2 hours ago by SomeonecoolLovesMaths
Source: Azerbaijan Junior National Olympiad 2021 P1
At least how many numbers must be deleted from the product $1 \times 2 \times \dots \times 22 \times 23$ in order to make it a perfect square?
1 reply
Nuran2010
4 hours ago
SomeonecoolLovesMaths
2 hours ago
smo 2018 open 2nd round q2
dominicleejun   7
N 2 hours ago by Kyj9981
Let O be a point inside triangle ABC such that $\angle BOC$ is $90^\circ$ and $\angle BAO = \angle BCO$. Prove that $\angle OMN$ is $90$ degrees, where $M$ and $N$ are the midpoints of $\overline{AC}$ and $\overline{BC}$, respectively.
7 replies
dominicleejun
Aug 15, 2019
Kyj9981
2 hours ago
Integer polynomial commutes with sum of digits
cjquines0   41
N Apr 27, 2025 by joshualiu315
Source: 2016 IMO Shortlist N1
For any positive integer $k$, denote the sum of digits of $k$ in its decimal representation by $S(k)$. Find all polynomials $P(x)$ with integer coefficients such that for any positive integer $n \geq 2016$, the integer $P(n)$ is positive and $$S(P(n)) = P(S(n)).$$
Proposed by Warut Suksompong, Thailand
41 replies
cjquines0
Jul 19, 2017
joshualiu315
Apr 27, 2025
Integer polynomial commutes with sum of digits
G H J
Source: 2016 IMO Shortlist N1
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
cjquines0
510 posts
#1 • 8 Y
Y by Davi-8191, samrocksnature, megarnie, ImSh95, Rounak_iitr, Adventure10, Mango247, deplasmanyollari
For any positive integer $k$, denote the sum of digits of $k$ in its decimal representation by $S(k)$. Find all polynomials $P(x)$ with integer coefficients such that for any positive integer $n \geq 2016$, the integer $P(n)$ is positive and $$S(P(n)) = P(S(n)).$$
Proposed by Warut Suksompong, Thailand
This post has been edited 1 time. Last edited by Amir Hossein, Jul 19, 2017, 5:11 PM
Reason: Added the proposer.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
v_Enhance
6877 posts
#2 • 16 Y
Y by Davi-8191, Taha1381, v4913, MountainC, samrocksnature, megarnie, HamstPan38825, ImSh95, Rounak_iitr, Fatemeh06, Adventure10, Stuffybear, NicoN9, Kendrick1401, Upwgs_2008, Funcshun840
The answer is $P(x) = c$ where $c \in \{1, \dots, 9\}$ as well as $P(x) = x$. Obviously they work.

First, note that $P$ is eventually nonnegative (by taking $S(n)$ large), so the leading coefficient of $P$ is positive. Thus let \[ P(x) = a_d x^d + \dots + a_0. \]
Main idea: we now plug in \[ n = 9 \cdot 10^e \]where $e$ is sufficiently large (say, $e > |a_d| + \dots + |a_0| + 2016^{d+100}$). We obtain then that \[ \sum_k a_k 9^k = P(9) = S(P(n)). \]Now, if any of the $a_i$ is negative, then $P(n)$ will have a string of at least $e - O(1)$ $9$'s in its decimal representation, contradiction. So all $a_i$ are nonnegative. For $e$ large enough the decimal representation of $P(n)$ then consists of the decimal representation of each $a_k 9^k$, separated by several zeros. In other words we have that \[ \sum_k a_k 9^k = \sum_k S(a_k 9^k). \]However, we know $m \ge S(m)$ for each positive integer $m$, with equality if and only if $m \in \{0, 1, 2, \dots, 9\}$. Thus $a_k 9^k \in \{0, 1, \dots, 9\}$ for every $k$. This implies that $a_0 \in \{0, \dots, 9\}$, $a_1 \in \{0,1\}$ and $a_k = 0$ for $k \ge 2$. From here we recover the solution set from before.
This post has been edited 1 time. Last edited by v_Enhance, Sep 3, 2017, 5:15 PM
Reason: P = 0 doesn't work
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
uraharakisuke_hsgs
365 posts
#3 • 4 Y
Y by samrocksnature, ImSh95, Rounak_iitr, Adventure10
My solution
$S(P(n)) = P(S(n))$ . Plug in $n = 10^k-1$ then $P(9k) = S(P(10^k-1)) \leq 9 (log (P(10^k-1))+1)$
Let $P(x) = a_rx^r+...+a_0$ then $P(n) < a_rn^{r+1}$ for $n$ big enough . Then $9(log (P(10^k-1))+1) < 9(log(a_r(10^k-1)^{r+1})+1) < 9((r+1)log(10^k)+1+log(a_r)) = 9((r+1)k+1+log(a_r))$
So $P(9k) < 9(k(r+1)+1+log(a_r))$ for all $k $. Then the degree of $P$ is atmost $1$
When $deg$ $P = 1$. Let $P(x) = ax+b$ . Then $S(an+b) = aS(n)+b \implies S(a.10^k+b) = S(a)+S(b) = a+b$ . Then , $a,b$ has only 1 digit . Also , $a+S(a+b)=S(a)+S(a+b)=S(a.(10^k+1) +b)=2a +b \implies S(a+b) = a+b$
$a+S(2a+b)=S(a(10^k+2)+b)3a+b \implies S(2a+b) = 2a+b$ . Similary we have $S(9a+b) = 9a+b$ . Then , $a = 1 , b = 0$
Then , $P(x) = x$. If $P$ is constant then $P \equiv c$ with $c$ has only one digit
This post has been edited 4 times. Last edited by uraharakisuke_hsgs, Sep 14, 2017, 10:55 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
62861
3564 posts
#4 • 6 Y
Y by e_plus_pi, MountainC, samrocksnature, ImSh95, Adventure10, Mango247
Answer. $P(x)$ is either a constant $1, \dots, 9$, or $P(x) = x$.

Let $P(x) = a_d x^d + a_{d - 1} x^{d - 1} + \dots + a_0$.

Set $n = 10^k$ for $k$ large. Then, $S(P(10^k)) = P(1)$: $S(P(10^k))$ is constant for $k$ large. This means that all coefficients of $P$ are nonnegative (otherwise, $P(10^k)$ would have long strings of nines, meaning $S(P(10^k))$ unbounded).

Now consider $n = m 10^k$ for $k$ large. Then $S(P(m  10^k)) = P(S(m))$, or
\[S(a_d m^d 10^{kd} + a_{d - 1} m^{d - 1} 10^{k(d - 1)} + \dots + a_0) = P(S(m))\]or, if $k$ is large enough,
\begin{eqnarray*}
S(a_d m^d) + S(a_{d - 1} m^{d - 1}) + \dots + S(a_0) & = & P(S(m))\\
& = & a_d S(m)^d + a_{d - 1} S(m)^{d - 1} + \dots + a_0.
\end{eqnarray*}However, observe that for each $i$,
\[S(a_i m^i) \le S(a_i) S(m)^i \le a_i S(m)^i.\]Summing the above inequality over $i = \{0, \dots, d\}$, observe that equality holds. Thus, we have equality: $S(a_i m^i) = a_i S(m)^i$ for all $i$ and $m$.

Now, we classify $a$ and $i$ such that $S(a m^i) = a S(m)^i$ for all $m$. This equality holds iff the product $a \cdot \underbrace{m \cdots m}_{i}$ has no carries in base ten. Note that $m = 1$ gives $S(a) = a$, so $a \in \{0, \dots, 9\}$. If $a = 0$, the equality always holds, so assume $a \ge 1$.
  • If $i = 0$, then the equality is $S(a) = a$, so $a \in \{1, \dots, 9\}$.
  • If $i = 1$, then the equality is $S(am) = aS(m)$; if $a \ge 2$, then $m = 9$ gives a contradiction. If $a = 1$, the equality is true.
  • If $i \ge 2$, then the equality is $S(a m^i) = a S(m)^i$, but selecting $m = 9$ will give carries, so the equality is not possible.

Thus, we deduce that for $S(a m^i) = a S(m)^i$ to hold for every $m$, either
  • $a = 0$,
  • or $(a, i) = (1, 0), \dots, (9, 0), (1, 1)$.
It follows that
  • $P(x) = 1, \dots, 9$, or
  • $P(x) = x, x + 1, \dots, x + 9$.
It is clear that the constant polynomials $1, \dots, 9$ and $P(x) = x$ work. Now suppose $P(x) = x + c$, with $c \in \{1, \dots, 9\}$: we have
\[S(n + c) = S(n) + c\]for all $n \ge 2016$, which is obviously false.

The solutions are constants $P \in \{1, \dots, 9\}$ and $P(x) = x$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
purplish
299 posts
#6 • 4 Y
Y by samrocksnature, ImSh95, Adventure10, Mango247
I have this problem solved except in the case that $P$ is linear, someone please give me a hint (only a hint, I do not want the problem spoiled for me) on how to proceed if $P$ is linear?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Vfire
1354 posts
#7 • 4 Y
Y by samrocksnature, hunghzkill180605, ImSh95, Adventure10
Can someone check if this works?

I claim that the only solutions are $P(x)=x$ and $P(x) = k$ where $\{0 \le k \le 9 \mid k \in \mathbb{N}\}$. Clearly these solutions all work.

Let $P(x) = a_0  + a_1 x+a_2x^2 + a_3 x^3 + \cdots + a_t x^t$. Now take $n = 9 \cdot 10^k$ where $k$ is greater than the number digits of $\max(a_0, 9a_1, \cdots, 9^ta_t)$. Then notice that $P(S(n)) = a_0 + 9a_1 + \cdots + 9^t a_t$ so
\begin{align*}
a_0 + 9a_1+81a_2 + \cdots + 9^t a_t &= S(P(n)) \\ &= S(a_0 + 9a_1 \cdot 10^k  + \cdots + 9^ta_t \cdot 10^{10k}) \\ &= S(a_0) + S(9a_1) + \cdots + S(9^ta_t)
\end{align*}Since $S(p) \le p$ for all integers $p$, we must have $a_i = 0$ for $2 \le i \le a_t$. Moreover, $0 \le a_0 \le 9$ and $0 \le a_1 \le 1$.

It suffices to show that $P(n) = x+a_0$ where $1 \le a_0 \le 9$ does not work. Simply take $n = 2019$ so we have $12+a_0 = S(2019 + a_0)$. Checking, we see that there are no solutions for $1 \le a_0 \le 9$ so we are done. $\blacksquare$
This post has been edited 1 time. Last edited by Vfire, Apr 17, 2018, 4:42 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
HKIS200543
380 posts
#8 • 3 Y
Y by samrocksnature, ImSh95, Adventure10
Vfire wrote:
Can someone check if this works?

I claim that the only solutions are $P(x)=x$ and $P(x) = k$ where $\{0 \le k \le 9 \mid k \in \mathbb{N}\}$. Clearly these solutions all work.

Let $P(x) = a_0  + a_1 x+a_2x^2 + a_3 x^3 + \cdots + a_t x^t$. Now take $n = 9 \cdot 10^k$ where $k$ is greater than the number digits of $\max(a_0, 9a_1, \cdots, 9^ta_t)$. Then notice that $P(S(n)) = a_0 + 9a_1 + \cdots + 9^t a_t$ so
\begin{align*}
a_0 + 9a_1+81a_2 + \cdots + 9^t a_t &= S(P(n)) \\ &= S(a_0 + 9a_1 \cdot 10^k  + \cdots + 9^ta_t \cdot 10^{10k}) \\ &= S(a_0) + S(9a_1) + \cdots + S(9^ta_t)
\end{align*}Since $S(p) \le p$ for all integers $p$, we must have $a_i = 0$ for $2 \le i \le a_t$. Moreover, $0 \le a_0 \le 9$ and $0 \le a_1 \le 1$.

It suffices to show that $P(n) = x+a_0$ where $1 \le a_0 \le 9$ does not work. Simply take $n = 2019$ so we have $12+a_0 = S(2019 + a_0)$. Checking, we see that there are no solutions for $1 \le a_0 \le 9$ so we are done. $\blacksquare$

I think you are assuming that all the $a_i$ positive here. Of course this is fixable
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
little-fermat
147 posts
#9 • 8 Y
Y by pavel kozlov, Ali3085, Sanyalswastik, samrocksnature, ImSh95, Rounak_iitr, Adventure10, Mango247
Plugging $n=10^k$ we get : $P(1)=S(P(10^k))$ which implies all the cofficients of $P$ are nonnegative
We will use $S(a+b)\le S(a)+S(b)$ with equality when there is no carry in the addition $a+b$

Let $P(x) = a_d x^d + a_{d - 1} x^{d - 1} + \dots + a_0$
$S(P(x))=S(a_d x^d + a_{d - 1} x^{d - 1} + \dots + a_0)\le S(a_d x^d) + S(a_{d-1} x^{d-1}) + \dots + S(a_0)\\
\le a_dS(x^d) + a_{d-1}S(x^{d-1}) + \dots + a_0\le a_dS(x)^d + a_{d-1}S(x)^{d-1} + \dots + a_0=P(S(x))$

So we have : $S(x^i)=S(x)^i\implies$ ther is no carry in the addition : $\underbrace{x+x+\dots+x}_{x^{i-1}}$
Plugging $x=6666\implies i={0,1}$

Also we have : $S(a_ix^i)=a_iS(x^i)\implies$ ther is no carry in the addition : $\underbrace{x^i+x^i+\dots+x^i}_{a_i}$
Plugging $x=6666\implies a_i=\{0,1\}$ where $1 \le i\le d$
So either $P(x)=c$ easily we get $0 \le c\le 9$ is a solution
Or $p(x)=x+c\implies S(n)+c=S(n+c)\implies c=0$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
urdoom
3 posts
#10 • 4 Y
Y by samrocksnature, ImSh95, Adventure10, Mango247
Let $P(x) = a_n x^n + \cdots + a_2 x^2 + a_1 x + a_0$. As $P(x)$ is positive, so $a_n$ (being the coefficient of the highest power of $x$) must be non-negative.
Putting in $x = 10^k$, where $k > max(a_n, \dots, a_2, a_1, a_0)$ gives us:
$S(P(10^k)) = P(S(10^k)) \Rightarrow S(a_n 10^{nk} + \cdots + a_2 10^{2k} + a_1 10^k + a_0) = P(1) = a_n + \cdots + a_2 + a_1 + a_0 \Rightarrow S(P(10^k))$ becomes constant for large k. If any of $a_i$, where $0 \le i \le n$ are negative, there will be a string of $9$s in the number, which will increase in length (and hence, the sum will also increase) as $k$ becomes larger, which is a contradiction. Therefore, all $a_i \ge 0$.
Putting in $x = 9 \cdot 10^k$, where $k > max(9^n a_n, \dots, 81a_2, 9a_1, a_0)$ gives us:
$S(9^n \cdot 10^{nk} a_n + \cdots + 81 \cdot 10^{2k} a_2 + 9 \cdot 10^{k} a_1 + a_0) = P(9) = 9^n a_n + \cdots 81 a_2 + 9 a_1 + a_0$
$\Rightarrow S(9^n a_n) + \cdots + S(81 a_2) + S(9 a_1) + S(a_0) = 9^n a_n + \cdots 81 a_2 + 9 a_1 + a_0$.
Since we have $S(t) \le t$ with equality holding if and only if $t \in \{0, 1, 2, \dots, 9\}$, so all of $a_i = 0$, for $i \ge 2$, $a_1 \in \{0, 1\}$ and $a_0 \in \{0, 1, 2, \dots, 9\}$, otherwise the expressions above cannot be equal.
Case 1:
$P(x) = x + a_0 \Rightarrow S(x + a_0) = S(x) + a_0$, for $x \ge 2016$, which is obviously only true when $a_0 = 0$, leading us to the solution $P(x) = x$.
Case 2:
$P(x) = a_0$ which obviously works given the above conditions.
So, $P(x) = x$ and $P(x) = c$ where $c \in \{0, 1, 2, \dots, 9\}$ are the only solutions.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
monkeycalculator
362 posts
#11 • 3 Y
Y by samrocksnature, ImSh95, Adventure10
Claim: $P(n) = n$ or $P(n) = t$ for any $t \in \{ 1, \ldots , 9 \}$ are the only solutions.
Clearly, these solutions does work.
$S(k) \leq k$, with equality occurring while $1 \leq k \leq 9$, which is obvious.
Let $P(n) = \sum_{i}a_i n^i$. Chose arbitrary $k$ such that $10^k > \max(a_i)$, which is positive since leading coefficient is positive.
$$S(P(10^k)) = P(S(10^k))$$$$S(\sum_{i}a_i (10^k)^i) = P(1) = \sum_{i}a_i$$First, see that each coefficient is non-negative, or else taking large $k$ will make there exists a large amount of $9$'s in its decimal representation and thus $P(1)$ arbitrarily large, contradiction.
Then, notice that since $10^k > a_i$, there is no carry-over while taking the sum, so we have:
$$S(\sum_{i}a_i (10^k)^i) = \sum_{i} S(a_i)$$Thus, we find that $\sum_{i} S(a_i) = \sum_{i}a_i$ which means that $a_i \in \{ 0, 1, \ldots , 9 \}$
Now, chose $t$ with $1 \leq t \leq 9$ and arbitrary $k$ such that $10^k > \max(a_i t^i)$. Then,
$$S(\sum_{i}a_i (t \cdot 10^k)^i) = P(S(t \cdot 10^k)) = P(t) = \sum_{i}a_i t^i$$Likewise, we obtain:
$$ \sum_{i} S(a_i t^i) = \sum_{i} a_i t^i$$This implies that $1 \leq a_i t^i \leq 9$ for any $t \mid 1 \leq t \leq 9$.
It is trivial to see that the only possible $a_i t_i$ are $t=0$ or $t=1, a_i = 1$.
So, we have $P(n) = an + t$ for any $t \in \{ 0, 1, \ldots , 9 \}$ and $a \in \{ 0, 1 \}$.
We can easily verify that that out of the $20$ solutions in this form, only $P(n) = n$ or $P(n) = t$ for any $t \in \{ 1, \ldots , 9 \}$ works. So, these are the only solutions.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
VulcanForge
626 posts
#12 • 4 Y
Y by samrocksnature, ImSh95, Adventure10, Mango247
The answer is $P(x) = x$ for all $x$ or $P(x) = m$ for all $x$, for some $m \in \{1, 2, \dots , 9 \}$.

If $P(x)$ is always a constant $m$, then we have $S(m) = m$, which easily implies that $m \in \{1, 2, \dots , 9\}$.

Now assume that $\text{deg}(P) \geq 2$, and we will derive a contradiction. In the given equation take $n = 10^k-1$ for arbitrarily large $k$; then we get $S(P(10^k-1)) = P(9k)$. Note that $S(P(10^k-1)) \leq 9(\text{log}_{10} (P(10^k-1))+1)$. Thus we have $P(9k) \leq 9(\text{log}_{10} (P(10^k-1))+1) \Rightarrow 10^{\frac{P(9k)}{9}} \leq P(10^k-1)+1$. Let $\text{deg}(P)  = d$. Note that for large enough $x$, we have $P(x)+1 < P(x+1) < x^{d+1}$. Thus we have $10^{\frac{P(9k)}{9}} < 10^{k(d+1)}$. But obviously $\frac{P(9k)}{9} > k(d+1)$ for large enough $k$, so we have $10^{\frac{P(9k)}{9}} > 10^{k(d+1)}$, contradiction.

Now we do the case $\text{deg}(P) = 1$. Let $P(x) = ax+b$ for an integer $b$ and a positive integer $a$. We previously derived that $10^{\frac{P(9k)}{9}} \leq P(10^k-1)+1$ for large enough $k$; thus we have $10^{ak+\tfrac{b}{9}} \leq a (10^k-1)+b+1$. But if $a>1$ then the LHS is greater than the RHS for sufficiently large $k$. Thus $a=1$, and $P(x) = x+b$. But by the given we then have $S(x+b) = S(x)+b$; taking $x = 10^m$ for sufficiently large $m$, we have $S(b)+1 = b+1 \Rightarrow S(b) = b$, so $b \in \{0, 1, 2, \dots, 9 \}$. Taking $x = 109$ eliminates all positive values of $b$; thus we can only have $P(x) = x$, and we are done as claimed.
This post has been edited 1 time. Last edited by VulcanForge, Dec 23, 2019, 8:19 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
math_pi_rate
1218 posts
#13 • 3 Y
Y by amar_04, samrocksnature, ImSh95
Nice and easy! Here's my solution: The case when $P$ is constant (say $P \equiv C$) gives $S(C)=C$, and so $1 \leq C \leq 9$ ($C \neq 0$ so as to make $P$ positive). From now on assume that the degree of $P$ is $d\geq 1$, and write $P(x)=\sum_{i=0}^d a_ix^i$ with $a_d>0$ (since $\lim_{x \mapsto \infty} P(x)=\infty$). Putting $n=10^k$ in the given equation (for $k>3$), we get $$a_0+a_1+ \dots +a_d=P(1)=P(S(10^k))=S(P(10^k))=S(a_0+10^ka_1+ \dots +10^{kd}a_d)$$By taking $k> \max_{0 \leq i \leq d} \lfloor \log(a_i) \rfloor$, we can get all $a_0,a_1, \dots ,a_d$ in different blocks when $P(10^k)$ is written. If any of the $a_i$'s is negative, then we will get arbitrarily long chains of $9$'s in $P(10^k)$, and so $S(P(10^k))$ will eventually exceed $P(1)$. So all $a_i$'s must be non-negative. In particular, this means that $P$ is strictly increasing for all $x>0$ (here we can say "strictly" since $a_d>0$). So for all sufficiently large $m$, there exists a unique $x_0>0$ such that $P(x_0)=10^m$. Applying the problem condition for $n=x_0$ then gives $P(S(x_0))=1$. But, $S(x_0) \geq 1$ implies that $P(S(x_0)) \geq P(1)$. Thus, we get $$0<a_0+a_1+ \dots +a_d \leq 1 \Rightarrow a_0=a_1= \dots =a_{d-1}=0 \text{ and } a_d=1$$Hence, $P(x)=x^d$, and so the problem condition translates to $S(n^d)=S(n)^d$. Putting $n=8000$ gives $S(8^d)=8^d$, and so we must have $d \leq 1$. Thus, the only solutions are $P=\text{id}$ and $P \equiv 1,2, \dots ,9$. $\blacksquare$
This post has been edited 2 times. Last edited by math_pi_rate, Apr 6, 2020, 11:55 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Severus
742 posts
#14 • 2 Y
Y by samrocksnature, ImSh95
This was surprisingly easy...

The answer is $P(x)=a$ where $a\in\{1,2,3,4,5,6,7,8,9\}$ or $P(x)=x$.

Let us assume that $P(x)=\sum_{i=0}^m a_ix^i$ for integers $a_i$. Now if some $a_i$ are negative, then if we let $n=10^k$ for some sufficiently large $k$ (like $k>\max(a_1,a_2,\dots,a_m)$), then $S(P(10^k))=P(S(10^k))=P(1)$. But $P(1)=\sum_{i=0}^m a_i$ and $S(P(10^k))=\text{Sum of non-negative terms } a_i+\text{ other positive stuff } \neq P(1)=\text{Sum of non-negative terms } a_i+\text{ sum of negative terms } a_j$. Hence all $a_i$ are non-negative.
Then choose $n=9\cdot 10^k$ for some suitably very large $k$ (specifically, $k>\max( a_i\cdot9^i)$ for $i=0,1,\dots,9$ would suffice) and so $P(S(n))=P(9)=\sum_{i=0}^{m}a_m\cdot9^m$ and $S(P(n))=\sum_{i=0}^{m}S(a_m\cdot9^m)$.
Now we know that $n\geq S(n)$ for all non-negative integers $n$ with equality holding only when $n$ is a single digit. Also for $i>1$, since $9^i$ is greater than a single digit number, so $\sum_{i=0}^{m}a_m\cdot9^m=\sum_{i=0}^{m}S(a_m\cdot9^m)$ only if for all $i>1$, $a_i=0$ and $a_1\in\{0,1\}$ and $a_0\in\{0,1,2,3,4,5,6,7,8,9\}$, since for $a_i>1$, $9a_1$ is not a single digit number.
Now if $a_1=1$, then we have for all $n>2016$, $S(P(n))=S(n+a_0)=P(S(n))=S(n)+a_0$. Now put $n=10000-a_0$ to get $S(10000)=1=S(10000-a_0)+a_0$. Since $S(10000-a_0)>0$ this is only possible if $a_0=0$. So $P(x)=x$ is a solution.
Otherwise $a_1=0$ and so $P(x)=a_0$ where $a_0\in\{1,2,3,4,5,6,7,8,9\}$ since $P(n)$ is positive for $n\geq 2016$. We see that this $P$ also works.
Hence we are done. $\square$
This post has been edited 2 times. Last edited by Severus, May 18, 2020, 12:15 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
rd123
473 posts
#15 • 5 Y
Y by samrocksnature, ImSh95, Mango247, Mango247, Rounak_iitr
Solution with porkemon2.

We claim that $P(x) \equiv c$ for $c \in \{1,2,3,4,5,6,7,8,9 \}$ or $P(x) \equiv x$.

Plug in $n=10^k$ for large $k$ to get $S(P(10^k))=P(1)$, so $S(P(10^k))$ is constant, so $P$ has only nonnegative integer coefficients, since otherwise we would get a ton of $9$s and as we increase $k$ we get more $9$s.

Now we plug in $10^k-1$ for large $k$. This gets us $S(P(10^k-1))=P(9k)$. Note that $P(10^k-1)=O(10^{kd})$, so $S(P(10^k-1))$ is $O(k)$, while $P(9k)=O(k^d)$, so this implies that $d \leq 1$. Let $P(x) \equiv ax+b$.

This means that$$S(an+b)=aS(n)+b.$$We plug in $n=10^k+9$ for large $k$ to get$$S(a \cdot 10^k + 9a +b)=10a+b,$$or $S(a)+S(9a+b)=10a+b$. This means $S(9a+b)=9a+b$, since the sum of the digits of a number is at most that number itself. This means $9a+b$ is a single digit number. Then either $a=0,b \in \{1,2,3,4,5,6,7,8,9 \}$ or $a=1,b=0$, which give the desired solution set. (Note that if $a=b=0$ then $P$ won't take positive values.)
This post has been edited 1 time. Last edited by rd123, Jun 1, 2020, 5:15 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Aryan-23
558 posts
#17 • 2 Y
Y by samrocksnature, ImSh95
Plug in $n=10^k$ for large $k$ . This gives :
$$ P(1) = S(P(10^k))$$; implying that all the coefficients of $P(x)$ are non-negative . Now we plug in $n=9\cdot 10^k$ for large $k$ , we have that $$S(P(9 \cdot 10^k))=P(9)$$
Assume $P(x) = \sum_{i=0}^{d} a_i x^i  $ with $a_i\ge 0$

Note that $P(9\cdot 10^k)$ is an integer composed of the integers $a_d\cdot 9^d , a_{d-1}\cdot 9^{d-1} \dots a_0 $ with some zeroes between them . So we have

$$\sum_{i=0}^{d} S(a_i \cdot 9^i)= S(P(9 \cdot 10^k)) = P(9) = \sum_{i=0}^{d} a_i \cdot 9^i$$
However note that $S(x) \leq x$ , with equality iff $0\leq x \leq 9$ . This means that $0\leq a_i \cdot 9^i \leq 9$ for all $2 \le i \le d$ . In particular , this means that $a_i=0$ for all $i \leq 2$ . Hence $\operatorname {deg} P \leq 1$ .
Note that if $P(x) = ax+b$ with $a,b>0$ then we have that $a \leq 1$ . If $a=1$ , then choose $n= 10^k + (10-b)$ . We have :
$$ S(P(n))= S( 10^k+10) = 2 \neq 11 = P(11-b) = P(S(n)) \rightarrow \leftarrow$$
This leaves us with $P(x)=x$ for all $x$ or $P(x) = c$ for some $1\leq c \leq 9$ , for all $x$ . Its easy to see that these work . We are done . $\blacksquare$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
bissue
302 posts
#18 • 3 Y
Y by samrocksnature, ImSh95, Mango247
basic idea is that regrouping is bad, I think? this solution is so awfully written that I'm starting to doubt whether I've actually solved the problem or not
We claim that the only such polynomials $P(x)$ are $P(x)=x$ and $P(x)=c$, where $c$ is a positive integer between $1$ and $9$, inclusive.

If $P(x)$ has any negative coefficients, $P(10^n)$ for sufficiently large $n$ will contain arbitrarily long chains of $9$s in its decimal representation, so it is impossible for $S(P(10^n))=P(S(10^n))=P(1)$ to be true for all $n$. Therefore, $P(x)$ must contain only nonnegative coefficients.

Now we use the case of $n=9999$ to argue the rest. It is important to recognize that, for any nonnegative integers $a$ and $b$, $S(a+b) \leq S(a) + S(b)$, and $S(ab) \leq S(a) \cdot S(b)$. In particular, if any regrouping is involved when computing $a+b$ or $ab$, these inequalities are strict. Now, if we assume $P(x) = a_1 x^{b_1} + a_2 x^{b_2} + \cdots + a_s x^{b_s}$ is degree $2$ or higher, we then have
\begin{align*}
S(P(9999)) & = S(a_1 \cdot 9999^{b_1} + a_2 \cdot 9999^{b_2} + \cdots + a_s \cdot 9999^{b_s}) \\
& \leq S(a_1 \cdot 9999^{b_1}) + S(a_2 \cdot 9999^{b_2}) + \cdots + S(a_s \cdot 9999^{b_s}) \\ 
& < a_1 \cdot S(9999)^{b_1} + a_2 \cdot S(9999)^{b_2} + \cdots + a_s \cdot S(9999)^{b_s} = P(S(9999))
\end{align*}where the inequality is strict because $a_i \cdot 9999^{b_i}$ involves regrouping when $b_i \geq 2$, so $S(a_i \cdot 9999^{b_i}) < a_i \cdot S(9999)^{b_i}$. This is a contradiction, so $P(x)$ must be linear or constant. The cases for $P(x)$ linear or constant are different because the regrouping is not necessarily required, so we still need to consider these cases.

If $P(x)=c$ for some constant $c$, it must be that $S(c)=c$, which is only true for $c \in \{1, 2, \cdots, 9\}$. These nine solutions are all valid.

If $P(x)$ is linear, we can again argue using the case of $n=9999$ by noting that $S(c \cdot 9999) < c \cdot S(9999)$ for all integers $c > 1$, so if the coefficient of $x$ in $P(x)$ were greater than $1$, it would then be that $S(P(9999)) < P(S(9999))$, a contradiction, so we must have $P(x)=x+c$ for some constant $c$. Using $n=9999$ one final time, we see that $c$ must equal $0$, since any larger $c$ would cause regrouping, which would then imply $S(P(9999)) < P(S(9999))$. Therefore, the only linear solution is $P(x)=x$.
This post has been edited 1 time. Last edited by bissue, Feb 25, 2021, 10:04 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
AwesomeYRY
579 posts
#19 • 4 Y
Y by samrocksnature, ImSh95, Mango247, Rounak_iitr
I claim that the solutions are $P(x)=x$, or $P(x)=c$ where $c$ is some single digit number, which both clearly work.

Lemma: $S(x)\leq x$, with equality at $x\leq 9$
Proof: If $x>10$, then $S(x)\leq x-9<x$, a contradiction. Clearly, if $x\leq 9$, then $S(x)=x$.$\square$

Write $P(x)=a_0+a_1x+a_2x^2+a_3x^3+\dots a_dx^d$.

First, plug in $n=10^x$ where $x>a_i$.
\[P(1)=P(S(10^x))=S(P(10^x)) \]This gives us that all $a_i\geq 0$ because otherwise we produce 9s

Thus, we must have that $a_i=s(a_i)$ and all $a_i$ are nonnegative.

Now, we plug in $n=9\cdot 10^{x}$ for some $x$ such that $\forall i, x>a_i$, then we have
\[S(P(9\cdot 10^x)) =S(a_0)+S(9\cdot 10^x*a_1)+\ldots S((9*10^x)^d*a_d)= S(a_0)+S(9*a_1)+\ldots S(9^d*a_d)\]\[P(S(9\cdot 10^x)) = P(9)=a_0+9a_1+\ldots 9^da_d\]Since we still have
\[S(P(9\cdot 10^x))=P(S(9\cdot 10^x))\]due to our lemma, this tells us that $9^ia_i\leq 9$ for all $i$. This tells us that $a_0\leq 9$ and $a_1\leq 1$, and for $i\geq 2, a_i=0$.

Note that if $a_1=0$, then we have the $P(x)=c$ case. We now take $a_1=1$, writing $P(x)=x+a_0$. We now take $n=9999$, which gives
\[P(S(9999))=P(36)=36+a_0\]Now, if $a_0=0$, then we have the $P(x)=x$ case, so take $a_0\geq 1$, so
\[S(P(9999)) = S(9999+a_0) = S(10000+(a_0-1)) = a_0 < 36+a_0 = P(S(9999))\]A contradiction. Thus, we have shown that $P(x)=x$, and $P(x)=c$ where $c\leq 9$ are the only solutions and we are done$\blacksquare$.
This post has been edited 1 time. Last edited by AwesomeYRY, Apr 9, 2021, 7:31 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
blackbluecar
302 posts
#20 • 2 Y
Y by Elyson, ImSh95
Let $P(x)=a_nx^n+\cdots+a_1x+a_0$. Notice that $S(P(10^k))=P(1)$

Claim 1: All coefficients in $P$ are non-negative

Assume the contrary. Clearly, the leading coefficient is positive. Assume the coefficient of $x^{m+1}$ is positive and $x^m$ is negative. As $c$ grows large, we see $a_{m+1}(10^c)^{m+1}+a_m(10^c)^m$ gets many non-zero digits between them. Thus, $S(P(10^c))$ grows arbitrarily large. Contradiction. $\square$

Claim 2: $\deg P \leq 1$

Assume the contrary. For sufficiently large $N$ we have...

$S(a_0+9a_1+ \cdots +9^na_n)$

$=S(a_0+(9\cdot 10^N)a_1+\cdots (9 \cdot 10^N)^na_n)$

$=S(P(9\cdot 10^N))$

$=P(9)$

$=a_0+9a_1+ \cdots +9^na_n$

Thus, $P(9)$ is a digit. By assumption, $n \geq 2$. Recall $a_n$ is positive so, $9^na_n \geq 81a_n>10$ which is too large to be a digit. $P(9)>81a_n>10$ so can't be a digit. Contradiction. $\square$

Recall $S(a_0+9a_1)=a_0+9a_1$. If $a_1 \geq 2$ then $S(a_0+9a_1)=a_0+9a_1 >10$ and can't be a digit. So, $a_1$ is $0$ or $1$. If $a_1=0$ then any digit $a_0$ clearly works. If $a_1=1$ we have $a_0+9 \leq 9$ implying $a_0=0$. So, either $P(x)=c$ for some digit $c$ or $P(x)=x$.
This post has been edited 3 times. Last edited by blackbluecar, Jul 8, 2021, 3:25 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
bora_olmez
277 posts
#21 • 1 Y
Y by ImSh95
Solved over 8 months ago but had to LaTex it so I will post a solution anyways.

Let $$P(x) = a_dx^d+a_{d-1}x^{d-1}+....+a_1x+a_0$$$\textbf{Claim:}$ $a_i \geq 0$ for all $d \geq i \geq 1$
$\textbf{Proof)}$
Take some sufficiently large $k > log(max(a_1,...,a_n))$ and let $n=10^k$ for some $k \in \mathbb{N}$, then $$ S(P(10^k)) = P(1)$$and assume FTSOC that $a_i < 0$ is the smallest $i$ satisfying the aforementioned inequality, then we have that the digits $\lceil log(a_{i-1})\rceil+1,...,ki-\lceil log(a_i) \rceil$ are all $9$ and therefore $S(P(10^k))$ can get arbitrarily large which is a contradiction. $\square$

Now, take $n = 9 \cdot 10^k$ for some large $k$ and note that $$\sum_{i=0}^{n} a_i \cdot 9^i = S(9) = S(P(n)) = S(\sum_{i=0}^{n} a_i \cdot 9^i) $$yet, $S(x) = x$ is only possible if $x \in \{0,..,9\}$ meaning that $S$ must be a constant in which case $S(x) = c$ for some $c \in \{0,..,9\}$ or $S(x) = x$. $\blacksquare$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
bluelinfish
1449 posts
#22 • 1 Y
Y by ImSh95
We claim the answers are $P(x)=c$ for $1\le c\le 9$ and $P(x)=x$, which clearly work. Let $P(x)=a_nx^n+a_{n-1}x^{n-1}+\ldots+a_1x+a_0$.

We will use the following fact. which is well-known:
Fact. If $x_1, x_2, \ldots, x_p$ are nonnegative integers, and $\sum_{i=1}^p S(x_i)=\sum_{i=1}^p x_i$, then both quantities are equal to an integer from $0$ to $9$, inclusive.

It is clear that the leading coefficient of $P$ must be positive. Plug in $x=9\cdot 10^j$ into the equation for all sufficiently large values of $j$. We get that $S(P(x))=P(S(x))=P(9)$, which is constant. If any of the coefficients of $P(x)$ are negative, then the sum of $S(P(x))$ for all sufficiently large $n$ cannot be the same (there will be a bunch of nines at one point), so all coefficients of $P$ must be nonnegative.

For sufficiently large $j$, there will be no carries between different terms, making $S(P(x))$ simply equal to $\sum_{i=0}^j S(a_i \cdot 9^i)$. However, this must be equal to $P(9)=\sum_{i=0}^j S(a_i \cdot 9^i)$. By the claim, both quantities (particularly $P(9)$) must be equal to an integer from $0$ to $9$, inclusive.

Given that the coefficients are positive integers, this reduces the possible values of $P(x)$ to nonnegative integers from $0$ to $9$ and $x$. Clearly $P(x)=0$ does not work, so we are done.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
ETS1331
107 posts
#23 • 1 Y
Y by ImSh95
The answer is $P(n) = c$ for integers $1 \leq c \leq 9$ and $P(n) = n$. It is trivial to show that these work. Furthermore, trivially throw out the case where $P$ is constant.

Now, write $P(n) = \sum\limits_{i=0}^{d} a_ix^i$, and furthermore define $T$ to be $\{i \mid i \in \mathbb{Z}, 0 \leq i \leq d, a_i \neq 0 \}$ (or, in english, all of the values $i$ such that $a_i$ is not $0$). Say $t_1 < t_2 < t_3 < \ldots < t_e$ are the elements of $T$ sorted in order; in particular, we have $2.718\ldots \neq e = \left|T\right|$. Therefore, we can also write $P(n) = \sum\limits_{i=1}^{e} a_{t_i} x^{t^i}$.

Claim: For all integer $1 \leq i \leq d$, $a_i \geq 0$.
Proof. Note that this is equivalent to proving that for every $1 \leq j \leq e$, $a_{t_j} > 0$, so we will prove this equivalent restatement. Assume, for the sake of contradiction, that there exists some $j$ where $a_{t_j} < 0$ (the two cannot be equal by definition). Take the largest such $j$. We have two cases: $j = e$, and $j < e$. If $j = e$, we note that $\lim\limits_{n \rightarrow \infty} P(n) = \lim\limits_{n \rightarrow \infty} a_{t_e}n^{t_e} =  - \infty$, so if we take a sufficiently large $n$ we will have $P(n) < 0$, contradiction.

If instead we have that $j < e$, then we let $n = 10^k$ for some very large $k$. Then, by the problem statement, we have \[ S(P(10^k)) = P(S(10^k)) = P(1) \]which implies that $S(P(10^k))$ must be constant even as $k$ grows large. However, we claim that $S(P(10^k))$ is in fact unbounded. To prove this, write: \[ P(10^k) = \sum\limits_{i=1}^{e} a_{t_i} 10^{kt_i} = \underbrace{a_{t_1}10^{kt_1} +  \cdots + a_{t_{j-1}}10^{kt_{j-1}} }_{\text{very small}} + a_{t_j} 10^{kt_j} + \underbrace{a_{t_{j+1}}10^{kt_{j+1}} + \cdots + a_{t_e}10^{kt_e}}_{\text{very big; positive}} \]Then, the first $j$ terms (i.e. the ``very small" terms and $a_{t_j} 10^{kt_j}$) are some negative number with far fewer than $kt_{j+1}$ digits, the number of $0$s present in the ``very big" terms. Thus, when the addition of the two parts (or rather, subtraction of two positive integers) is completed, there will be $\approx k (t_{j+1} - t_j) \geq k$ 9s created in the subtraction, which means the digit sum is unbounded when $k$ is large, contradiction. $\blacksquare$

Claim (Main): The only valid polynomials must be of the form $x+c$ for $0 \leq c \leq 9$.
Proof. Assume for the sake of contradiction that $P$ is a valid polynomial not of that form. We use a somewhat similar argument as in the second part of our previous claim. In particular, we take $n = 9 \cdot 10^k$ for $k$ very large. Then, we have: \[ S(P(9 \cdot 10^k)) =S\left(\sum\limits_{i=1}^{e} a_{t_i}9^{t_i}10^{kt_i}\right) = \sum\limits_{i=1}^{e} S\left(a_{t_i}9^{t_i} 10^{kt_i}\right) = \sum\limits_{i=1}^{e} S\left(a_{t_i} 9^{t_i} \right) \]where the second equality holds when $k$ is large enough, because there will be $0$s that ``seperate" each of the $e$ terms of the sum. However, this value is also equal to \[ P(S(9 \cdot 10^k)) = P(9) = \sum\limits_{i=1}^{e} a_{t_i} 9^{t_i}. \]However, it is easy to see (by basic induction, for instance) that $S(x) < x$ when $x \geq 10$. Therefore, if there exists some $a_{t_i} 9^{t_i} > 10$, then \[ \sum\limits_{i=1}^{e} a_{t_i} 9^{t_i} <  \sum\limits_{i=1}^{e} S\left(a_{t_i} 9^{t_i}\right), \]contradiction. However, this occurs whenever $t_i > 2$, or if $i = 1$ and $a_{t_i} \geq 2$, or if $i = 0$ and $a_{t_i} \geq 10$, which proves the claim. $\blacksquare$
Now, we can finally finish by showing that the polynomial $P(n) = n+c$ fails the given conditions. This is easy enough to see by plugging in the value $10^4 - c$; it is clear that \[ 37 = P(S(10^4 - c)) \neq S(P(10^4 - c)) = 1 \]and we are finally done.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
asdf334
7585 posts
#24 • 2 Y
Y by ImSh95, Mango247
The answer is $P(x)=x$ and $P(x)=c$ for all integers $1\le c\le 9$. It's easy to show that these work.

Now suppose that the degree of $P$ is at least $2$. Consider $n=10^a-1$ for sufficiently large $a$. Then let the term with the largest degree in $P(x)$ be $cx^k$. Note that $S(n)=9a$ while $P(n)<10c(10^a-1)^k$ since $a$ is sufficiently large (which causes the effects of terms of smaller degree to be negligible). We have that the digit sum of $P(n)$ is, say, at least $\frac{c(9a)^k}{10}$ (since $a$ is sufficiently large). Suppose that $10c(10^a-1)^k$ has $d$ digits. Then we must have that $9d\ge \frac{c(9a)^k}{10}$. But now, the LHS increases linearly and since $k\ge 2$ this inequality must be violated for sufficiently large $a$.

Now suppose that $P$ is constant. Then it's easy to show that if $P(x)=c$ we must have $1\le c\le 9$. Finally, suppose that $P$ is linear. Let $P(x)=ax+b$. Take $n=9999$ to get
\[36a+b=S(9999a+b).\]It follows that $9999a+b$ has at least $4a+\frac{b}{9}$ digits. Then, we have
\[9999a+b\ge 10^{4a+\tfrac{b}{9}-1}.\]Fix $a\ge 2$. I claim that we must have
\[10^{4a+\tfrac{b}{9}-1}>9999a+b.\]Clearly this holds for $b=0$. Incrementing $b$ by $1$ multiplies the LHS by $10^{\tfrac{1}{9}}$ and increases the RHS by $1$. The LHS will increase by at least $10^7\left(10^{\tfrac{1}{9}}-1\right)$. Therefore, it suffices to show that
\[10\ge (10^{-7}+1)^9\]which is true by the Binomial Theorem. Finally, we must have $a=1$, which implies that $S(n)+b=S(n+b)$ for all $n\ge 2016$. Take $n=10^x-b$ for sufficiently large $x$; then the RHS is $1$ while the LHS is at least $b+1$. Then $b=0$ which gives $P(x)=x$. We are done. $\blacksquare$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
awesomeming327.
1711 posts
#25 • 1 Y
Y by ImSh95
Let $y\ge 4$ be an integer and $x\in\{0,1,2\dots,9\}$ then we have \[S(P(x\cdot 10^y))=P(x).\]Let $S(n)=a_mn^m+a_{m-1}n^{m-1}+\dots+a_1n+a_0$ and let $y$ be large enough so that $10^y$ exceeds $|a_mx^m|+|a_{m-1}x^{m-1}|+\dots+|a_1x|+|a_0|.$ Then, we claim the value $P(10^y)$ will be \[\overline{a_ma_{m-1}\dots a_0}.\]This holds unless there are negative terms, but if there are negative terms then increasing $y$ would result in more nines being added, contradicting $S(P(10^y))=P(1).$ Thus, we know that $P(x)$ has nonnegative coefficients and that \[S(P(x\cdot 10^y))=S(a_0)+S(xa_1)+S(x^2a_2)+\dots+S(x^ma_m)=P(x)=a_0+xa_1+\dots+x^ma_m\]Note that $S(c)\le c$ for all $c$ with equality if and only if $c\in\{0,1,2,\dots,9\}$ so $S(a_0)=a_0,S(xa_1)=xa_1, S(x^ia_i)=x^ia_i.$ Now, this implies $a_0\in \{0,1,\dots,9\}$ and letting $x=9$ we get $a_1\in \{0,1\}$ and $a_i=0$ for $i\ge 2.$ Thus, $P(x)=c,c\in\{0,1,\dots,9\}$ or $P(x)=x+c,c\in\{0,1,\dots,9\}.$ The second option yeilds \[S(x+c)=S(x)+c\]but simply use something like $10^y-1$ to ensure that only $c=0$ is possible option. Now, checking shows that the possible solutions are: $P(x)=c,c\in\{1,\dots,9\}$ or $P(x)=x.$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
lrjr24
967 posts
#26 • 1 Y
Y by ImSh95
The solutions are $P(x)=c$ where $c \in \{ 1,2,3, \dots , 9\}$, and $P(x)=x$.
Let $P(x)=a_dx^d+a_{d-1}x^{d-1} + \cdots + a_0$. Let $b \ge 4$ be an integer. Take $n=10^b$ so that $S(P(10^b))=P(1)$. If there is negative coefficients, take $b$ to be very big so that $\frac{a_i}{a_{i-1}} >> 10^b$ for all $i$. The negative term will make an arbitrarily large amount of $9$'s appear, so $P(1)$ is arbitrarily big, a contradiction since it is fixed. Thus all coefficients are nonnegative. We have that $P(10^b)=\overline{a_d 0 \dots 0 a_{d-1} 0 \dots 0 a_1 0 \dots 0 a_0}$. We have that $\sum_{i=0}^d a_i = P(1) = S(P(10^b)) = \sum_{i=0}^d S(a_i)$. Since $S(a_i) \le a_i$ with equality iff $a_i \in \{0,1,2 \dots , 9 \}$, so all the coefficients are one digit integers. Take $n=10^b \cdot \underbrace{1 1 \dots 1}_{10}$ with $b$ big enough. We have that $$\overline{a_da_{d-1} \dots a_0} = P(S(n)) = S(P(10^b \cdot \underbrace{1 1 \dots 1}_{10})) = S(\overline{\underbrace{a_d \cdots a_d}_{10} 0 \dots 0 \underbrace{a_{d-1} \cdots a_{d-1}}_{10} 0 \dots 0 \underbrace{a_1 \cdots a_1}_{10} 0 \dots 0 \underbrace{a_0 \cdots a_0}_{10}} = 10(a_d+a_{d-1}+ \cdots +a_0).$$If $d \ge 2$, then $81 \ge 9a_0 \ge 90 a_2 \ge 90$, a contradiction. If $d=0$, we obviously get the desired solutions. Now assume $P(n)=an+b$ with $a,b \in \{0,1,2, \dots , 9\}$. We have $aS(n)+b=S(an+b) \le S(an)+b \le aS(n)+b$. Thus $S(an+b)=S(an)+b$ and $aS(n)=S(an)$. Taking $n=9$ into the second equation we have $9a$ is a one digit integer, so $a=1$. Thus $S(n+b)=S(n)+b$. Taking $n=9$ again, we have $b=0$, so we get $P(x)=x$ is the only degree $1$ solution so we are done.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Iora
194 posts
#27 • 1 Y
Y by ImSh95
Fakesolve? My solution looks different than others, suspicious imo

Let $P(x)=\sum a_dx^d$ as usual and note that $a_d$ is positive since for bigger $x$ $P(x)$ should be positive. Assume $ d \ge 1$ since if $P$ is polynomial, it is clear that $P(x)=c  \ \forall c \in \{1,2,...,9 \} $ works.

Choose $n=\overline{b_k000...000b_{k-1}000..000b_{k-2}000...b_0} \cdot 10^e$ such that $\sum b_i= 10^m$ and $b_i \neq 0$. Now, choose arbitrarly bigger $k,e,m$ and arbitrarly bigger number of zeroes between $b_i,b_{i-1}$ hence $n$ is arbitrarly bigger.

Since by choice of $n$, if we multiply $n$ by some natural number, say $N$, then $N \cdot n$ will be equal $\overline{ (b_kN)000.000 (b_{k-1}N)000...000....000 (Nb_0)} \cdot 10^e$. Then $S(N \cdot n)= \sum b_iN= N \sum b_i= N \cdot 10^m$. Now lets calculate RHS.

Note that $S(n)=10^m$ by choice of $n$. Then $P(10^m)=\overline{a_d00...0a_{d-1}00...000....00a_0}$ since $m$ is very big. Now, calculate LHS:

$P(n)=\sum a_dn^d$. Note that by $10^e$, there are some zeroes between $a_in^i$ and $a_{i-1}n^{i-1}$. Then $S(P(n))=\sum S(a_in^i)$. By choice of arbitrarly bigger number of zeroes between digits, we can calculate $a_in^i$ as letting $N_i= a_in^{i-1}$, then $S(a_in^i)=S(N_i \cdot n)= N_i \cdot 10^m$. Doing the same thing repeteadly, We have $LHS= \overline{(N_d10^m)00...0000(N_{d-1}10^m)00...000.....a_0}$ while $RHS= \overline{a_d00...0a_{d-1}00...000....00a_0}$. The first digit from left of $RHS$ is $a_d$, hence the first digit of $a_dn^{d-1}=N$ is $a_d$. Then by choice of $n$ we must have $d=1$. After that, let $x=9 \cdot 10^d$ to conclude $\boxed{P(x)=x}$ is a possible solution, and it works hence we are done!

Note: uhh I just realized we should prove $a_i$ must be non-negative, it is fixable anyways
This post has been edited 1 time. Last edited by Iora, Nov 16, 2022, 9:27 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
JAnatolGT_00
559 posts
#28 • 1 Y
Y by ImSh95
We claim that only solutions are $P(x)=x$ and $P(x)=c$ for $c\in \mathcal A \left \{ 1,2,\dots,9 \right \},$ which obviously work.

Consider some satisfying polynomial $P(x)=\sum_{k=1}^d a_kx^k.$ Since $P$ is positive for arbitrary large integer $x\geq 2016$ it follows that $a_d>0.$ Plug $n=9\cdot 10^E$ for an arbitrary large $E;$ if $\exists b:a_b<0$ then the decimal representation of $P(n)$ contains a sufficently long substring consisting of digits $9,$ so $S(P(n))=P(9)$ is unbounded, contradiction; hence $a_i\geq 0.$ Then the decimal representation of $P(n)$ is a sequence of numbers $a_k9^k$ (for $k=1,2,\dots,d$) separated by zeroes; therefore $$\sum_{i=1}^d a_i9^i=P(9)=S(P(n))=\sum_{i=1}^d S(a_i9^i).$$Since for $m\in \mathbb Z^+$ we have $S(m)\leq m$ with holding equality only for $m\in \mathcal A,$ it follows that $a^k 9^k\in \mathcal A$ for each $k.$ Therefore $$a_0\in \mathcal A,\text{ } a_1\in \left \{ 0,1 \right \},\text{ }a_{i>1}=0,$$so it suffices to check all cases.
This post has been edited 1 time. Last edited by JAnatolGT_00, Dec 26, 2022, 6:17 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
cj13609517288
1900 posts
#29 • 1 Y
Y by ImSh95
Solved with cxyerl.
The answer is $\boxed{P(n)\equiv 1,2,3,4,5,6,7,8,9,n}$.

For what follows, let $k$ be a sufficiently large positive integer. I think $k=10^{665}\cdot(665^{\deg P}\cdot(\text{sum of the absolute values of all coefficients of P}+10^{665})+665)$ is good enough.

Claim. All of the coefficients of $P$ are nonnegative integers.
Proof. Obviously the leading coefficient is nonnegative. Assume FTSOC that some coefficient of $P$ is negative. Consider some positive integer $h>k$. If $n=10^{h}$, then $P(n)$ should have many $9$s in its decimal expansion. By increasing $h$, we can get arbitrarily many $9$s, therefore bloating $S(P(n))$ to infinity. However, $P(S(n))=P(1)$ is constant, contradiction.

Let $n=9\cdot 10^k$. Then
\[P(9)=S(a_0)+S(9a_1)+S(81a_2)+\dots\le a_0+9a_1+81a_2+\dots=P(9),\]equality case being $a_0$, $9a_1$, $81a_2$, etc all being a digit in base $10$, so $a_2=a_3=\dots=0$. This also means that $0\le a_0\le 9$ and $a_1\in\{0,1\}$. If $a_1=0$ then only $1\le a_0\le 9$ work, and if $a_1=1$ then $n=10^k+9$ gives $a_0=0$, which works. QED.

Remark. I had a really weird bounding solution beforehand, but cxyerl found a much cleaner finish!
This post has been edited 2 times. Last edited by cj13609517288, Jun 5, 2023, 2:03 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
vsamc
3789 posts
#30 • 3 Y
Y by ImSh95, megarnie, centslordm
Solution
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Pyramix
419 posts
#31
Y by
Note, the only constant polynomials that satisfy are $P\equiv c$ where $c\in\{1,2,\ldots,9\}$. Moreover, $P(n)=n$ satisfies as well. We claim that these are the only solutions.

Note that $n-S(n)\mid P(n) - P(S(n))$. So, $n-S(n)\mid P(n)-S(P(n))$. So, if $1\leq n\leq9$, then $1\leq P(n)\leq9$. More importantly, $P(9)\leq9$.
Suppose $P(n)=a_0+a_1n+\cdots+a_kn^k$
Fix $n=9\times10^j$, where $j$ is large enough. Then, $S(n)=9$ and we have $n-9\mid P(n)-S(P(n))$.
We take $j$ to be so large that there is no carry-over in the addition $a_0+a_1n+\cdots+a_kn^k$. Then, we have
$S(P(n))=S(a_0)+S(a_1n)+\cdots+S(a_kn^k)=S(a_0)+S(9a_1)+\cdots+S(a_k9^k)$
Since $S(n)=9$, we have $S(P(n))=P(9)$. This gives $a_0+9a_1+\cdots+a_k9^k=P(9)=S(a_0)+S(9a_1)+\cdots+S(a_k9^k)$
Note that $S(n)\leq n$ and equality holds iff $1\leq n\leq9$. So, we have $\{a_0,9a_1,\ldots,a_k9^k\}\subseteq\{1,2,\ldots,9\}$ which forces $a_2=a_3=\cdots=a_k=0$ and $a_1\in\{0,1\}$ and $1\leq a_0\leq 9$.
Checking gives the solutions mentioned. $\square$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
IAmTheHazard
5001 posts
#32 • 2 Y
Y by Rounak_iitr, centslordm
The answer is $P(x)=c$ where $1 \leq c \leq 9$ and $P(x)=x$, which clearly work.

Suppose that $P(x)=a_dx^d+\cdots+a_0$. Clearly $a_d$ is positive. Furthermore, by plugging in $n=10^k$ for large $k$, , we get that each coefficient is nonnegative, since if a negative coefficient exists by making $k$ large we may produce an unbounded number of digits equal to $9$ in $P(10^k)$, but $P(S(10^k))=P(1)$ is constant. Then, by plugging in $n=9\cdot 10^k$, we get that $S(P(9\cdot 10^k))=S(9^da_d)+\cdots+(9^0a_0)$ and $P(S(9\cdot 10^k))=P(9)=9^da_d+\cdots+9^0a_0$, hence each $9^ia_i$ must be at most $9$, implying that either $i=1$ and $a_i=1$ or $i=0$ and $a_i \leq 9$. Therefore we only have to prove that $P(x)=x+c$ for some $1 \leq c \leq 9$ is impossible. This is trivial by plugging in $n=10-c$. $\blacksquare$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
YaoAOPS
1537 posts
#33
Y by
Claim: $P$ must be linear.
Proof. Let $P(n) = a_d x^d + a_{d-1} x^{d-1} + \dots + a_0$.
Consider $n = c \cdot 10^N$. For a sufficiently large $N$, it follows that \[ \sum_{i=0}^{d} S(a_i \cdot c^i) = P(S(c)) \]As such, it follows that for $c = \overline{1111111 \dots 1}$ with $k$ $1$s, that for sufficiently large $N$ \[ \sum_{i=0}^{d} S(a_i \cdot k^i) = \sum_{i=0}^{d} S(a_i \cdot (10^{Nk} + \dots + 1)^i) \]Since $S(a) + S(b) \ge S(a + b)$, the RHS must be strictly greater, and inequality only holds when no caries occur when combining the right hand side. If $i > 1$, a contradiction arises from taking $k > 10$, after which a carry must occur. $\blacksquare$
As such, let $P(x) = ax + b$ so $S(ax + b) = aS(x) + b$.
As such, there again must be no carries when evaluating $S(ax + b)$, which only holds when either $a = 0$, and $S(b) = b$, or $a = 1$ and $b = 0$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
GrantStar
821 posts
#34 • 1 Y
Y by Rounak_iitr
The answer is $P(x)=x$ or $P(x)=k$ for $k=1,2,3,4,5,6,7,8,9$, which work. Let $P(x)=\sum_{i=1}^j a_ix^i$.

Claim: Every coefficient in $P$ is nonnegative
Proof. Note that the leading coefficient is positive as if not taking $S(n)$ sufficiently large gives a sign contradiction. Then, letting $n=10^k$ for large enough $k$ we obtain that by increasing $k$ we can get more and more $9$s in the decimal representation of $P(n)$ as there is a negative signed term directly following a positive signed one that is arbitrarily larger than it. $\blacksquare$

Claim: $P$ has degree $0$ or $1$.
Proof. Take $n=9\cdot 10^k$ again for sufficiently large $k$. Then, $P(S(n))=P(9)=\sum_{i=1}^ja_i9^i$. However, $S(P(n))=\sum_{i=1}^j S(a_i\cdot 9^i)$ since for large enough $k$ each $a_i 9^i$ doesnt overlap digits with any other. Then, $a_i\cdot 9^i\geq S(a_i\cdot 9^i)$ with equality iff $a_i\cdot 9^i$ is a single digit, but equality must hold everywhere from above. This implies that $d=\deg P\leq 1$ as if not $a_d\cdot 9^d>S(a_d\cdot 9^d)$. $\blacksquare$

Now, if $P$ is constant then $P(x)=1,2,\dots,9$. If not, then $P(x)=a_1x+a_0.$ From above, we know that $a_1\cdot 9_i$ is a single digit and hence $a_1=1$. Then, if $a_0\neq 0$ simply take $n=10^k-a_0$ to get a contradiction. Thus $P(x)=x$ or $P(x)=k$ for $k=1,2,3,4,5,6,7,8,9$, as desired.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Pyramix
419 posts
#35
Y by
Idea is to fix $S(n)$.

Take $n=10^k$. Then, $S(n)=1$ and RHS is constant, which is $P(1)$.
Let $P(x) = c_0 + c_1x + \cdots + c_dx^d$. Then, for arbitrarily large $k$, we have
\[S(P(10^k))=S(c_0)+S(c_1)+\cdots+S(c_d)=c_0+c_1+\cdots+c_d\]Similarly, for any $10>c>0$, we have for sufficiently large $k$,
\[S(P(c\cdot 10^k))=S(c_0)+S(cc_1)+\cdots+S(c_dc^d)=c_0+c_1c+\cdots+c_dc^d\]Hence, $c_i=0$ for $i>1$ and $c_1=0,1$.

Only constant polynomials are one digit constants.

The only linear polynomial is $x+t$, and plugging in original equation gives $t=0$. So, $P(x)=x$.
Hence,
\[P(x)\in\left\{x,1,2,\ldots,9\right\}\]
This post has been edited 2 times. Last edited by Pyramix, Apr 3, 2024, 2:27 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
thdnder
197 posts
#36
Y by
Answer: $P(x) = x$ or $P(x) = c$, where $c \in \{1, 2, \dots, 9\}$.

Firstly, we'll show that $\deg(P) \le 1$. Assume the contrary, let $P(x) = a_kx^k + a_{k-1}x^{k-1} + \dots + a_1x + a_0$ for some $k \ge 2$. Replacing $P(x) \to -P(x)$, we may assume $a_k > 0$. Let $N$ be a large enough number and take $n = 10^N - 1$. Then $S(n) = 9N$, so $P(S(N)) = P(9N)$ and $P(n) < (a_k+1)n^k < (a_k + 1)10^{Nk}$. Since $PS(P(n)) \le 9(\log_{10}(P(n)) + 1) < 9(\log_{10}(a_k + 1) + Nk + 1)$, we see that $P(9N) < 9Nk + c$ for some constant $c$, contradicting the fact that $N$ is large enough and $\deg(P) \ge 2$. Thus, we may assume $\deg(P) \le 1$.

Case 1: $\deg(P) = 1$.

Let $P(x) = ax + b$ for some $a, b \in \mathbb{Z}$. Take $n = 10^N + k$ for some large $N$ and some $k \ge 2016$. Then, $a + S(ak + b) = a + aS(k) + b = aS(n) + b = S(an + b) = S(a) + S(ak + b)$, so $a = S(a)$, which means that $a \in \{1, 2, \dots, 9\}$. Thus taking $n = 10^N + k$ for some large $N$, we get that $a + aS(k) + b = aS(n) + b = S(an + b) = S(a) + S(ak + b) = a + S(ak + b)$, so $aS(k) + b = S(ak + b)$ for all $k \ge 0$. Plugging $k = 0$ into this, we see that $b = S(b)$, which means that $b \in \{1, \dots, 9\}$. Now for $0 \le k \le 9$, $ak + b = S(ak + b)$, so $9a + b \in \{0, 1, \dots, 9\}$ and $9a + b \ge 9$, so $a = 1$ and $b = 0$, which means that $P(x) = x$.

Case 2: $\deg(P) = 0$.

In this case, we get that $c = P(x) = S(c)$, so $c \in \{0, 1, \dots, 9\}$.

So $P(x) = x$ or $P(x) = c$ for some $c \in \{1, \dots, 9\}$. $\blacksquare$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
ezpotd
1262 posts
#37
Y by
I claim the solutions are $P(x) = c$ for $1 \le c \le 9$ and $P(x) = x$, both of which clearly work.

Let $n = 9999999 \dots$ where the $9$ is repeated $k$ times. Then $P(S(n)) = P(9k)$. Now $S(P(n)) \le (9 \log P(n) + 1) \sim 9k + a$ for some constant $a$. Since the $S(P(n))$ is linear or smaller in $k$, we see that $P(S(n)) = P(9k)$ is linear or smaller in $k$, so $P$ is linear. We then have $cS(n) + d = S(cn + d)$. Substitute $n = 9$, then have $9c + d = S(9c + d)$, this only has single digit solutions (manually observe that $10$ thru $20$ has no solutions, after that all $2$ digits have sum at most $18$ but the value is greater than $20$, after that we generally have $9k < 10^{k- 1}$), so we have $9c + d \ge 9 $, so either we have $c = 0$ and $d$ a single digit, giving the working constant solutions, otherwise we have $c = 1, d = 0$, giving $P(x) = x$, which works.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Maximilian113
574 posts
#38
Y by
Let $P(x) = a_mx^n+a_{m-1}x^{m-1}+\cdots + a_1x^1+a_0.$ Suppose for the sake of a contradiction that there is some $a_i < 0.$ Letting $n=10^k$ for some arbitrarily large positive integer $k$ gives $P(1)=S(P(10^k)).$ But as $k$ increases $P(10^k)$ gets more and more $9$s and hence its sum of digits goes to infinity, a contradiction. Therefore all $a_i \geq 0.$

Now, notice that letting $n=9 \cdot 10^k$ for some arbitrarily large positive integer $k$ yields $$\sum_{i=0}^n S(a_i9^i) = P(9) = \sum_{i=0}^n a_i9^i.$$However, note that if a positive integer $x$ has $d \geq 3$ digits then $$S(x) \leq 9d < 10^{d-1} \leq x.$$Meanwhile, if $d=2$ and $x > 18$ then $S(x) \leq 18 < x.$ If $10 \leq x \leq 18,$ we have $S(x) \leq 1+8 = 9 < x.$ Therefore, for all $x \geq 10$ we have that $S(x) < x.$ Meanwhile for $1 \leq x \leq 9$ clearly $S(x) = x.$

With this, if $n \geq 2$ we clearly have $$\sum_{i=0}^n S(a_i9^i) < \sum_{i=0}^n a_i9^i,$$which is a contradiction. Thus $n \leq 1,$ in this case equality must hold so we have $S(a_0)=a_0$ and $S(9a_1)=9a_1.$ From the first equation, we have $0 \leq a_0 \leq 9.$ From the second equation, we have $a_1 = 0,1.$

If $a_1=0,$ $P(x)=a_0$ and this clearly works.

If $a_1=1,$ $P(x)=x+a_0.$ If $1 \leq a_0 \leq 9,$ then letting $n=10-a_0$ yields $$a_0+S(10-a_0)=S(10)=1$$which is clearly impossible. Thus $a_0 = 0$ and $P(x)=x.$ This solution clearly works.

Hence, the only solutions are $P(x)=a_0$ where $0 \leq a_0 \leq 9$ or $P(x)=x.$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
onyqz
195 posts
#39
Y by
cute one
solution
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
HamstPan38825
8857 posts
#40
Y by
This is not very interesting: the answers are just $P \equiv c \in \{1, 2, \dots, 9\}$ and $P \equiv x$, which work vacuously. Now let $n = 10^N - 1$ for some very large positive integer $N$. We may assume that the leading coefficient $a_d$ of $P$ is positive. For $d = \deg P$, we have \[S(P(n)) \leq 9 \log_{10} P(n) \leq 9 \log_{10} \left(a_d n^d P(1)\right) = 9d \log_{10} n +C < 9dN + C\]where $C$ is a constant. On the other hand, $P(S(n)) = P(9N) > \tfrac 12 a_d(9N)^d$ is strictly greater than the previous if $d \geq 2$.

So we must have $d = 1$; then we have $P(S(n)) = 9a_d N - C$, so $a_d = 1$ is forced too, and we get the desired solution set.
This post has been edited 1 time. Last edited by HamstPan38825, Mar 2, 2025, 3:24 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
lelouchvigeo
181 posts
#41 • 1 Y
Y by alexanderhamilton124
solution
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
scannose
1012 posts
#42 • 1 Y
Y by alexanderhamilton124
cjquines0 wrote:
For any positive integer $k$, denote the sum of digits of $k$ in its decimal representation by $S(k)$. Find all polynomials $P(x)$ with integer coefficients such that for any positive integer $n \geq 2016$, the integer $P(n)$ is positive and $$S(P(n)) = P(S(n)).$$
Proposed by Warut Suksompong, Thailand
first note that $P(n)$ cannot be constant oops this isn't true, assume $P(n)$ isn't constant for the rest of this proof. let the leading term of $P(n)$ be $ax^b$ for a pair of positive integers $(a, b)$, and let $n = 10^m - 1$ for some arbitrarily large positive integer $m$ satisfying $a(m')^b > 2|f(m') - a(m')^b|$ for all $m' \geq m$ (the proof that such a $m$ exists is omitted).

then, we have $$P(n) < 1.5a \cdot 10^{bm} \implies S(P(n)) < 9bm \log (1.5a)$$; however, on the other hand, we have $$P(S(n)) = P(9m) > 0.5a(9m)^b.$$if $b \geq 2$, there must exist an arbitrarily large value of $m$ such that $0.5a(9m)^b > 9bm \log(1.5a)$, contradiction; therefore, we conclude $b = 1$.

rewrite $P(x)$ as $ax + c$, and take another sufficiently large integer $y$ such that $10^y > a, |c|$. if $c < 0$, comparing $x = 10^y$ and $x = 10^{y+1}$ gives $P(S(10^y)) = P(1) = P(S(10^{y+1}))$, but $S(P(10^{y+1})) = S(P(10^y)) + 9$, reaching a contradiction; therefore, we may assume $c \geq 0$. now, plugging in $x = 10^y$ gives $S(P(10^y)) = S(a) + S(c) = P(1) = a + c$; this implies that $a, c < 10$. then, plugging in $x = 9 \cdot 10^y$ gives $S(9a) + S(b) = 9a + b$, implying $a = 1$. finally, plugging in $x = 2019$ gives $S(2019 + b) = 12 + b$, which only holds when $b = 0$.

therefore, the only non-constant polynomial satisfying the given condition is $P(x) = x$, which obviously works. if $P(x)$ is constant, it is easy to see that the only possible values of $P(x)$ are $1, 2, 3, 4, 5, 6, 7, 8, 9$.

this solution is more messy than i'd like it to be, please lmk if i fakesolved this problem
This post has been edited 1 time. Last edited by scannose, Mar 2, 2025, 5:32 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
ihategeo_1969
225 posts
#43
Y by
Yah I definitely overcooked this...

We first prove that if $\deg(P) \ge 2$, then there are no solutions.

Claim: There exists a polynomial $Q(x)$ which has exactly $1$ negative coefficient and a leading positive coefficient but $P(Q(x))$ has all non-negative coefficients.
Proof: Key idea is to choose \[Q(x)=Ax^4+Ax^3-x^2+Ax+A \text{ where $A \gg 0$}\]If $Q(x)=Ax^4+Ax^3+AX+A$ then this would have almost worked because if $A$ is too massive then the coefficients of $P$ won't really matter as long as its leading coefficient is positive.

But obviously $Q$ needs to have a negative coefficient, so just adding $-x^2$ will not do anything as we can keep taking $A$ bigger and bigger and the ``resistance" won't matter. $\square$

For large $n$, we have $s(P(Q(10^n)))=s(P(Q(10^{n-1})))$ but $s(Q(10^n))=s(Q(10^{n-1}))+9$. And so we have \[O(1)=s(P(Q(10^n)))=P(s(Q(10^n)))=P(9n+O(1))\]which is a contradiction.

Now we take two cases.
  • If $\deg(P)=0$. Let $P=c$ so $s(c)=c \iff c \in \{1,\dots ,9\}$.
  • If $\deg(P)=1$. Let $P(x)=ax+b$ so $s(an+b)=as(n)+b$. Again we take $n \to 10^n$ (for large $n$), by the same thing above we automatically dismiss the case where $b$ is negative and if $b \ge 0$ then we have $s(a)+s(b)=a+b$ so $a \le 9$. Now put $n \to a10^n$ for large $n$ and again we so again $s(a^2)+s(b)=a^2+b$ so $a^2 \le 9$. Continue doing this so $a^k \le 9$ for all $k$ which forces $a=1$. This also means $b=0$.
Hence only solutions (which obviously work) are \[\boxed{P(x) \equiv x} \text{ AND } \boxed{P(x) \equiv c} \text{ where $c \in \{1,\dots,9 \}$}\]
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
joshualiu315
2533 posts
#44
Y by
The answer is $P(x) = \boxed{c, x}$ where $c \in \{0,1,2\dots,9\}$, which obviously work.

Suppose that $P(x) = a_0+a_1x+\dots+a_nx^n$. Plug in $n = 10^k$, to get

\[P(1) = a_0+a_1+\dots+a_n = S(P(10^k)) \ge 0.\]
Thus, all of the coefficients are nonnegative. Then, plug in $n = 9 \cdot 10^k$ for an extremely large $k$. This gives us

\begin{align*}
P(9) = a_0+9a_1+9^2a_2 + \dots + 9^na_n &= S(a_0 + 9 \cdot 10^k a_1 + 9^2 \cdot 10^{2k}a_2+\dots 9^n10^{nk}a_n) \\
&= S(a_0)+S(9 a_1)+S(9^2a_2)+\dots + S(9^na_n).
\end{align*}
Since $S(n) \le n$, so we need $S(9^ia_i) = 9^ia_i$ for all $i$. Hence, $a_i = 0$ for all $i \ge 2$ and $0 \le a_1 \le 1$.

If $a_1=0$, obviously all values $0 \le a_0 \le 9$ work. Else, we plug in $n=2019$ to get

\[12+a_0 = S(2019+a_0),\]
which can obviously only be satisfied if $a_0 = 0$.
Z K Y
N Quick Reply
G
H
=
a