Two positive integers are called anagrams if every decimal digit occurs the same number of times in each of them (not counting the leading zeroes). Find all non-constant polynomials $P$ with non-negative integer coefficients so that whenever $a$ and $b$ are anagrams, $P(a)$ and $P(b)$ are anagrams as well. Proposed by Sutanay Bhattacharya
Problem
Source: India EGMO TST 2025 Day 1 P2
Tags: algebra, polynomial
MrOreoJuice
14.12.2024 10:16
The answer is $P(x) = x$.
Let $a=9\cdot 10^p + 1$ and $b = 10^p + 9$, since $P(a)$ and $P(b)$ are anagrams, we must have $P(b) < P(a) \le 10P(b)$, now dividing by $P(b)$ and taking limit $p \to \infty$ on both sides yields that $1 < 9^n \le 10$ where $n = \deg P$, so $n = 1$.
Now we come to the annoying part of the problem. Let $P(x) = ax+b$ where $a=\overline{a_1\cdots a_p}$ (assume $p \ge 2$ for now) and $b=\overline{b_1\cdots b_q}$, considering anagrams \[x_1 = 1\underbrace{0\cdots 0}_{m+p+1}1 \underbrace{0\cdots 0}_{n+q} ~~ ~~ ~~ ~~ ~~ x_2 = 1\underbrace{00\cdots 00}_{m+n+p+q+1}1\]where $m,n$ are extremely large, we see that
\[P(x_1) = a_1\cdots a_p \underbrace{0\cdots 0}_{m} a_1\cdots a_p \underbrace{0 \cdots 0}_n b_1\cdots b_q\]\[P(x_2) = a_1\cdots a_p \underbrace{00\cdots 00}_{m+n+p+q}a_1\cdots a_p + b_1\cdots b_q\]implying $\overline{a_1\cdots a_p} + \overline{b_1\cdots b_q}$ should give a number with digits $a_1 , \dots , a_p , b_1 , \dots b_q$ (of course, the number of zero digits in $P(x_1)$ and $P(x_2)$ should match as well but as of now a lighter condition should do the job).
Note that this means $10^{p+1} + 10^{q+1} > a+b > 10^{p+q-1}$ which doesn't hold true for $p \ge 3$ and it is necessary $q < 3 \implies p = 2, q \le 2$. (Haven't checked further but pretty sure a casework bash will solve this part and prove no such $a,b$ exist).
From our initial assumption we can strengthen the condition to $p = 1$ and taking similar $x_1,x_2$ we can again get that $a + \overline{b_1\cdots b_q}$ should be made up of digits $a,b_1,\dots , b_q$. Assume for the sake of contradiction $b \neq 0$.
If $b$ is a single digit then $a+b > 9 \implies $ there must be a carry over of $1$ but then if one of $a,b$ is $1$ the other must be $9$ but this doesn't work.
Suppose $q \ge 2$. Again we must have $a + b_q > 9$ meaning there must be a carry over of $1$ on $b_{q-1}$ and $1 + b_{q-1} > 9 \implies b_{q-1} = 9$ and likewise $b_{q-2} = \cdots = b_2 = b_1 = 9$ but then the number $a+b$ will have lot's of zero digits and atmost one $9$ digit which is a contradiction.
Therefore $P(x) = ax$ where $a \in [1,9]$ and it can be manually checked that only $a=1$ works.
YaoAOPS
14.12.2024 10:25
Note that $P(9 \cdot 10^k + 1)$ and $P(10^k + 9)$ have the same number of digits, which is clearly false if $\deg P \ge 2$ since $P(9 \cdot 10^k+1)^2 > 10 \cdot P(10^k + 9)^2$ holds asymptotically. Then it's easy to see $P(x) = ax + b$ and that $a = 10^k$ must hold, and then by considering say $10^k + 10^{b} - b, 10^k + 10^{k-1-2b} \cdot (10^b - b)$ for large $k$ that $b < 10^k$.
Ankoganit
15.12.2024 02:23
$P(x)=10x+2$
satisfies the conditions of the problem. I haven't had time to check the arguments in detail to see what the problem is. I'll post my original solution when I get the chance.
chronondecay
15.12.2024 02:27
Both answers above are missing some solutions (at the time of this post); here's the fix. By the same arguments as above, we have $P(x)=ax+b$ for some $a>0$, $b\ge0$. First we solve the case of $a=1$:
Clearly $b=0$ works. Also, $b=1$ fails by taking for example $x=19,91$.
If $b>1$, take $x=10^n-b$ for $n$ large, so $x+b=10^n$ has $n+1$ digits. But $x$ has a digit which is not 9, so $x$ has an anagram $x'<x$. Now $x'+b<10^n$ has fewer than $n+1$ digits, so no value of $b>1$ works.
We now solve the general case:
Let
\begin{align*}
x_n&=1\underbrace{00\ldots0}_n\underbrace{99\ldots9}_n,\\
y_n&=\underbrace{99\ldots9}_n\underbrace{00\ldots0}_n1.
\end{align*}Now for each $n\ge1$, we have $x_n,y_n$ are anagrams, so $P(x_n),P(y_n)$ are also anagrams; in particular they have the same number of digits, say $k_n$. Thus
\begin{align*}
ax_n+b&\ge10^{k_n-1},\\
ay_n+b&<10^{k_n}.
\end{align*}Hence
$$\frac{ay_n+b}{10^{2n+1}}<10^{k_n-(2n+1)}\le\frac{10(ax_n+b)}{10^{2n+1}}.$$Now take $n\to\infty$; the first and last terms above both go to $a$, so we must have $k_n-(2n+1)$ constant for all large $n$. Calling this constant $c$, we conclude that $a=10^c$.
Write $b=10^cb'+b_0$ for some $b',b_0\ge0$ with $b_0<10^c$. Note that the digits of $ax+b=10^c(x+b')+b_0$ are formed by the union of the digits of $x+b'$ and the digits of $b_0$. Hence $P(x)$ preserves anagrams if and only if the polynomial $Q(x)=x+b'$ also preserves anagrams, and by the easy case above we must have $b'=0$.
Thus the complete set of solutions is given by $0\le b<a=10^c$.
quantam13
15.12.2024 15:57
Solved with Nimloth149131215208 The answer is $P(x)=10^c\cdot x+d$ where $c$ and $d$ are fixed constants satusfying $d<10^c$, which can easily be checked to work. Claim 1: $P$ is a linear polynomial. Proof. Notice that if $\deg P\ge 2$, then $\lim_{k\to\infty} \tfrac{P(9\cdot10^k+1)}{P(10^k+9)}>10$ so $P(9\cdot10^k+1)$ and $P(10^k+9)$ cant have the same number of digits $\blacksquare$ This allows us to take $P(x)=ax+b$. Claim 2: $a$ being one implies that $b$ is zero Proof. Say $b>0$. If $b=1$, consider $P(12)$ and $P(23)$ to get a contradiction. Otherwise, choose a sufficiently large $k$ and consider $$P(8\underbrace{99\dots 9}_{k})$$and $$P(\underbrace{99\dots 9}_{k}8)$$to get a contradiction. $\blacksquare$ Claim 3: If $a=10^c$ for some integer $c$, then implies that $b<10^c$ Proof. Say $b\ge 10^c$ and write $b=10^c\cdot q+r$ where $r<10^c$. Now this gives that $P(x)=10^c(x+q)+r$ but since $r$ is less than $10^c$, this is basically the same as "appending" $r$ to $x+q$, but $x+q$ is not an angaram preserving polynomial by Claim 2, which is our desired contradiction. $\blacksquare$ Thus by the previous claim, it suffices to prove $a$ is a power of $10$ to finish. Now set $m = 10^{2k} - 10^{k} + 1$ and $n = 10^{2k-1} + 10^{k} - 1$. It can be shown without much effort that these are both anagrams and that $\lim_{k\to\infty}\frac{m}{n}=10$. But by considering these two numbers and limits/size, its not so hard to get the desired conclusion, and thus we are done
Ankoganit
16.12.2024 03:39
Here's the solution I originally had in mind:
We claim that all such polynomials are of the form $P(x)=10^nx+r$ where $n$ is a non-negative integer, and $r<10^n$. It's easy to verify these indeed work.
We use the notation $x\sim y$ to denote $x$ and $y$ are anagrams. Now consider the numbers $a=9\cdot 10^n+1$ and $b=10^n+9$ for some $n>1$. Clearly $a\sim b$. Further, if $\deg P>1$, then $\lim_{n\to\infty}\frac{P(a)}{P(b)}>10$, which means $P(a)$ and $P(b)$ cannot have the same number of digits for large enough $n$.
Now assume $\deg P=1$, so that $P(x)=Ax+B$ for some integers $A>0$ and $B\ge 0$. Note that for any $x\sim y$, we have $x\cdot 10^n\sim y\cdot 10^n$, and if we choose $n$ so that $B$ has fewer than $n$ digits, we have $P(x\cdot 10^n)\sim P(y\cdot 10^n)$ implying $A\cdot x\cdot 10^n+B\sim A\cdot y\cdot 10^n+B$, so $Ax\sim Ay$ whenever $x\sim y$.
Now suppose $A$ has $n$ digits, $k$ of which are non-zero. Note that $$x=1\underbrace{0\dots 0}_{n-1\text{ 0's}}1\underbrace{0\dots 0}_{n-1\text{ 0's}}10\dots 1 \;\;(m \text{ 1's})$$and $$y=\underbrace{11\dots 1}_{m\text{ 1's}}\underbrace{00\dots 0}_{(m-1)(n-1)\text{ 0's}}$$are anagrams. Further, $Ax$ is $m$ copies of $A$ concatenated and thus has $km$ non-zero digits out of $mn$ total digits. Since $Ax\sim Ay$, $Ay$ also has $mn$ digits, but it has $(m-1)(n-1)$ trailing zeros, so at most $mn-(m-1)(n-1)=m+n-1$ non-zero digits. This implies $mk\le m+n-1\implies k\le 1+\frac{n-1}{m}$. Now taking $m$ large enough, this shows $k=1$.
Thus $A$ is of the form $a\cdot 10^n$ for some $a\in \{1,2,\dots,9\}$. The digit $a$ also satisfies $x\sim y\implies ax\sim ay$. But it's easy to check only $a=1$ has this property. So $A=10^n$ for some $n$.
Finally, let $B=q\cdot 10^n+r$ where $r<10^n$. Then $P(x)=10^n(x+q)+r$, and whenever $x\sim y$, we have $10^n(x+q)+r\sim 10^n(y+q)+r\implies 10^n(x+q)=10^n(y+q)\implies x+q\sim y+q$. Assume $q\ge 1$. Now consider anagrams $$x=1\underbrace{9\dots 9}_{N\text{ 9's}}\underbrace{0\dots 0}_{N\text{ 0's}}\sim y=1\underbrace{0\dots 0}_{N\text{ 0's}}\underbrace{9\dots 9}_{N\text{ 9's}}.$$For $N$ sufficiently large, it is clear that $x+q$ has more $9$'s than $y+q$, a contradiction.
Thus we must have $q=0$, and we have shown $P(x)=10^n x+r$ with $r<10^n$ as claimed.$\square$
L13832
15.01.2025 13:14
solution similar to #6 but still will post it as i liked this problem a lot
Note that $\deg(P)=1$ by using $P(9\cdot 10^k+1)>10\cdot P(10^k+9)$ for a proof by contradiction.
We can maybe generalize this a little to get the following:
Construction: $a=10^{2n}+9\cdot \sum_{i=0}^{n-1}10^i$ and $b=1+9\cdot \sum_{i=n+1}^{2n} 10^i$ (motivation)The construction is basically motivated because we need $a$ to approach to a power of 10.
Note that $P(a), P(b)$ will have the same number of digits (let that be $t$) then we have
\[P(a)/10^{2n+1}<10^{t-2n+1}\leq 10\cdot P(b)/10^{2n+1}\]as $n$ tends to $\infty$ we get $a=10^{k}$ where $k$ is constant as both sides of inequality approach $a$.
The proof will be finished if we show $b<a=10^k$, take $b=10^k\cdot b'+r, r<10^k$.
$ax+b=10^k(x+b')+r$ will be an angaram iff $x+b'$ is an anagram which gives $b'=0$ giving us $b=r$ implying our result.