2019 USAMO Problems/Problem 3

Problem

Let $K$ be the set of all positive integers that do not contain the digit $7$ in their base-$10$ representation. Find all polynomials $f$ with nonnegative integer coefficients such that $f(n)\in K$ whenever $n\in K$.

Solution

I claim the only such polynomials are of the form $f(n)=k$ where $k\in K$, or $f(n)=an+b$ where $a$ is a power of 10, $b\in K$, and $b<a$. Obviously, these polynomials satisfy the conditions. We now prove that no other polynomial works. That is, we prove that for any other polynomial $f$ with nonnegative coefficients, there is some $n\in K$ such that $f(n)\notin K$.

We first prove the result for monomials, polynomials in which only one coefficient is nonzero. This is obvious for constant polynomials $f(n)=k\notin K$. The next simplest case is $f(n)=an$ with $a$ not a power of 10, and hence $\lg a$ is irrational. By Dirichlet's approximation theorem, the set of multiples of $\lg a$ is dense $\bmod\ 1$, and thus contains an element with fractional part in the interval $[\lg 7,\lg 8)$. In other words, there is a power of $a$ whose decimal expansion starts with a 7. Let $a^x$ be the smallest power of $a$ that is not in $K$. Obviously, $x>0$, so letting $n=a^{x-1}$ completes the proof of this part.


We have now proven that for any $a$ that is not a power of 10, there is some $n\in K$ such that $an\notin K$. We proceed to the case where $f(n)=an^x$ for $x>1$. This splits into 2 cases. If $ax$ is not a power of 10, then pick $m\in K$ such that $axm\notin K$. For any $y$, we have \[f(10^y+m)=a10^{yx}+axm*10^{y(x-1)}+...+am^x\] If we choose $y$ to be large enough, then the terms in the expression above will not interfere with each other, and the resulting number will contain a 7 in the decimal expansion, and thus not be in $K$.

On the other hand, if $ax$ is a power of 10, then $a$ and $x$ are both powers of 10, and $x\ge10$. Obviously, $\frac12ax(x-1)$ is not a power of 10. By the previous step, which establishes the result for $x=2$, we can pick $m\in K$ such that $\frac12ax(x-1)m^2\notin K$. Then, for any $y$, \[f(10^y+m)=a10^{yx}+axm*10^{y(x-1)}+\frac12ax(x-1)m^2*10^{y(x-2)}+...+am^x\] Similarly, picking a sufficient large $y$ settles this case.


Now, we extend our proof to general polynomials. If a polynomial $f(n)=a_0+a_1n+a_2n^2+...+a_xn^x$ satisfies the conditions of the problem, then for any $m,y>0$: \[f(m*10^y)=a_xm^x*10^{yx}+...+a_1m*10^y+a_0\] Similarly, choosing $y$ to be sufficiently large results in the terms not interfering with each other. If $f$ contains any monomials that do not satisfy the conditions of the problem, then picking suitable $m$ and sufficiently large $y$ causes $f(m*10^y)$ to not be in $K$. Thus, $f$ is a linear polynomial of the form $ax+b$ where $a$ is 0 or a power of 10, and $b\in K$. It suffices to rule out those polynomials where $a>0$ and $b>a$. If this is the case, then since the digit of $b$ corresponding to $a$ is not 7, there must be a single-digit number $n$ such that the digit of $f(n)$ corresponding to $a$ is 7. Therefore, we are done.

-wzs26843545602

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

See also

2019 USAMO (ProblemsResources)
Preceded by
Problem 2
Followed by
Problem 4
1 2 3 4 5 6
All USAMO Problems and Solutions