What is the solution to Problem of the Week #207?

[Ackbach]

Here is this week's POTW:

-----

A repunit is a positive integer whose digits in base 10 are all ones. Find all polynomials $f$ with real coefficients such that if $n$ is a repunit, then so is $f(n)$.

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[Ackbach]

Re: Problem Of The Week # 207 - March 15, 2016

No one solved this week's POTW, which is from the 2007 Putnam archive. The solution, attributed to Kiran Kedlaya and his associates, follows:

Spoiler

Note that $n$ is a repunit if and only if $9n+1=10^m$ for some power of $10$ greater than 1. Consequently, if we set
$$g(n)=9f\left(\frac{n-1}{9}\right)+1,$$
then $f$ takes repunits to repunits if and only if $g$ takes powers of $10$ greater than $1$ to powers of $10$ greater than $1$. We will show that the only such functions $g$ are those of the form $g(n)=10^cn^d$ for $d\ge 0,\; c\ge 1-d$ (all of which work), which will mean that the desired polynomials $f$ are those of the form
$$f(n)=\frac19 (10^c(9n+1)^d-1)$$
for the same $c,d$.

It is convenient to allow "powers of $10$" to be of the form $10^k$ for any integer $k$. With this convention, it suffices to check that the polynomials $g$ taking powers of $10$ greater than $1$ to powers of $10$ are of the form $10^cn^d$ for any integers $c,d$ with $d\ge 0$.

Suppose that the leading term of $g(x)$ is $ax^d$, and note that $a>0$. As $x\to\infty$, we have $g(x)/x^d\to a;$ however, for $x$ a power of $10$ greater than $1$, $g(x)/x^d$ is a power of $10$. The set of powers of $10$ has no positive limit point, so $g(x)/x^d$ must be equal to $a$ for $x=10^k$ with $k$ sufficiently large, and we must have $a=10^c$ for some $c$. The polynomial $g(x)-10^cx^d$ has infinitely many roots, so must be identically zero.