olymmath

Putnam 2007 A4

  • Session A

A 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).

Curated text Kedlaya Putnam archive. Quoted with source.

Solutions

Human solution Solution 1 by almagest

The repunits are 101−19=1,102−19=11,103−19=111,…\frac{10^1-1}{9}=1,\frac{10^2-1}{9}=11,\frac{10^3-1}{9}=111,\dots.

So if nn is a power of 1010, then n−19\frac{n-1}{9} is a repunit, so f(n−19)f(\frac{n-1}{9}) is a repunit, and hence 9f(n−19)+19f(\frac{n-1}{9})+1 is a power of 1010.

But if f(x)f(x) is a polynomial, then g(x)=9f(x−19)+1g(x)=9f(\frac{x-1}{9})+1 is also a polynomial. Suppose its leading term is axkax^k.

Then lim⁡x→∞g(x)xk=a>0\lim_{x\to\infty}\frac{g(x)}{x^k}=a>0. But the sequence xm=10mx_m=10^m tends to infinity and each term g(xm)xmk\frac{g(x_m)}{x_m^k} is a power of 1010. The only limit point of the (positive and negative) powers of 1010 is 00. So g(xm)xmk\frac{g(x_m)}{x_m^k} must equal aa for all sufficiently large mm and aa must be a power of 1010. Suppose a=10ha=10^h (where h∈Zh\in\mathbb{Z}). Then g(x)−10hxkg(x)-10^hx^k has infinitely many zeros, so it must be identically zero.

Hence g(x)=10hxkg(x)=10^hx^k for some h∈Zh\in\mathbb{Z} and kk a non-negative integer. Hence f(x)=19(g(9x+1)−1)=19(10h(9x+1)k−1)f(x)=\frac{1}{9}(g(9x+1)-1)=\frac{1}{9}\left(10^h(9x+1)^k-1\right). That gives f(1)=19(10h+k−1)f(1)=\frac{1}{9}(10^{h+k}-1), so we require h≥1−kh\ge1-k.

A few examples may help:

k=0k=0 just gives the constant polynomials (where the constant is a repunit).

k=1k=1 gives the polynomials x,10x+1,100x+11x,10x+1,100x+11 etc.

k=2k=2 gives 110(9x2+2x−1)\frac{1}{10}(9x^2+2x-1), 9x2+2x9x^2+2x, 90x2+20x+190x^2+20x+1, 900x2+200x+11900x^2+200x+11 etc.

k=3k=3 gives 1100(81x3+27x2+3x−11)\frac{1}{100}(81x^3+27x^2+3x-11), 110(81x3+27x2+3x−1)\frac{1}{10}(81x^3+27x^2+3x-1), 81x3+27x2+3x81x^3+27x^2+3x, 810x3+270x2+30x+1810x^3+270x^2+30x+1 etc

Mathematics Stack Exchange. Open licence.

Human solution Solution 2 by Manjul Bhargava, Kiran Kedlaya and Lenny Ng

The terms of the source let olymmath link to this solution but not copy it. Read the solution (Kedlaya Putnam archive).

Similar problems

These problems have the most words in common with this statement.

Locator putnam/2007/a4 · Tag E984NAYTW2 · Edit this page on GitHub · Keys: j next, k previous