Maths Olympiad Prep

Library / /56 of 64

Algebra Difficulty 8.3 Shortlist Find the answer

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

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

Solution

Note that nn is a repunit if and only if 9n+1=10m9n+1 = 10^m for some power of 10 greater than 1. Consequently, if we put
g(n)=9f(n19)+1, g(n) = 9f\left( \frac{n-1}{9} \right) + 1,
then ff takes repunits to repunits if and only if gg takes powers of 10 greater than 1 to powers of 10 greater than 1. We will show that the only such functions gg are those of the form g(n)=10cndg(n) = 10^c n^d for d0d \geq 0, c1dc \geq 1-d (all of which clearly work), which will mean that the desired polynomials ff are those of the form
f(n)=19(10c(9n+1)d1) f(n) = \frac{1}{9}(10^c (9n+1)^d - 1)
for the same c,dc,d.

It is convenient to allow "powers of 10" to be of the form 10k10^k for any integer kk. With this convention, it suffices to check that the polynomials gg taking powers of 10 greater than 1 to powers of 10 are of the form 10cnd10^c n^d for any integers c,dc,d with d0d \geq 0.

\textbf{First solution:}
Suppose that the leading term of g(x)g(x) is axdax^d, and note that a>0a>0. As xx \to \infty, we have g(x)/xdag(x)/x^d \to a; however, for xx a power of 10 greater than 1, g(x)/xdg(x)/x^d is a power of 10. The set of powers of 10 has no positive limit point, so g(x)/xdg(x)/x^d must be equal to aa for x=10kx = 10^k with kk sufficiently large, and we must have a=10ca = 10^c for some cc. The polynomial g(x)10cxdg(x) - 10^c x^d has infinitely many roots, so must be identically zero.

\textbf{Second solution:}
We proceed by induction on d=deg(g)d = \deg(g). If d=0d=0, we have g(n)=10cg(n) = 10^c for some cc. Otherwise, gg has rational coefficients by Lagrange's interpolation formula (this applies to any polynomial of degree dd taking at least d+1d+1 different rational numbers to rational numbers), so g(0)=tg(0) = t is rational. Moreover, gg takes each value only finitely many times, so the sequence g(100),g(101),g(10^0), g(10^1), \dots includes arbitrarily large powers of 10. Suppose that t0t \neq 0; then we can choose a positive integer hh such that the numerator of tt is not divisible by 10h10^h. But for cc large enough, g(10c)tg(10^c) - t has numerator divisible by 10b10^b for some b>hb>h, contradiction.

Consequently, t=0t=0, and we may apply the induction hypothesis to g(n)/ng(n)/n to deduce the claim.

\textbf{Remark:} The second solution amounts to the fact that gg, being a polynomial with rational coefficients, is continuous for the 22-adic and 55-adic topologies on Q\mathbb{Q}. By contrast, the first solution uses the "\infty-adic" topology, i.e., the usual real topology.

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.