Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2019 USAMO Problems/Problem 3"

(Created page with "==Problem== Let <math>K</math> be the set of all positive integers that do not contain the digit <math>7</math> in their base-<math>10</math> representation. Find all polynomi...")
 
(→‎Solution)
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
 +
I claim the only such polynomials are of the form <math>f(n)=ax+b</math> where <math>a</math> is either 0 or a power of 10, and where <math>b\in K</math> and <math>b<a</math>. Obviously, these polynomials satisfy the conditions. We now prove that no other polynomial works. That is, we prove that for any other polynomial <math>f</math> with nonnegative coefficients, there is some <math>n\in K</math> such that <math>f(n)\notin K</math>.
  
 +
We first prove the result for monomials, polynomials in which only one coefficient is nonzero. This is obvious for constant polynomials <math>f(n)=k\notin K</math>. The next simplest case is <math>f(n)=an</math> with <math>a</math> not a power of 10, and hence <math>\lg a</math> is irrational. By Dirichlet's approximation theorem, the set of multiples of <math>\lg a</math> is dense <math>\bmod\ 1</math>, and thus contains an element with fractional part in the interval <math>[\lg 7,\lg 8)</math>. In other words, there is a power of <math>a</math> whose decimal expansion starts with a 7. Let <math>a^x</math> be the smallest power of <math>a</math> that is not in <math>K</math>. Obviously, <math>x>0</math>, so letting <math>n=a^{x-1}</math> completes the proof of this part.
 +
 +
 +
We have now proven that for any <math>a</math> that is not a power of 10, there is some <math>n\in K</math> such that <math>an\notin K</math>. We proceed to the case where <math>f(n)=an^x</math> for <math>x>1</math>. This splits into 2 cases. If <math>ax</math> is not a power of 10, then pick <math>m\in K</math> such that <math>axm\notin K</math>. For any <math>y</math>, we have
 +
<cmath>f(10^y+m)=a10^{yx}+axm*10^{y(x-1)}+...+am^x</cmath>
 +
If we choose <math>y</math> 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 <math>K</math>.
 +
 +
On the other hand, if <math>ax</math> is a power of 10, then <math>a</math> and <math>x</math> are both powers of 10, and <math>x\ge10</math>. Obviously, <math>\frac12ax(x-1)</math> is not a power of 10. By the previous step, which establishes the result for <math>x=2</math>, we can pick <math>m\in K</math> such that <math>\frac12ax(x-1)m^2\notin K</math>. Then, for any <math>y</math>,
 +
<cmath>f(10^y+m)=a10^{yx}+axm*10^{y(x-1)}+\frac12ax(x-1)m^2*10^{y(x-2)}+...+am^x</cmath>
 +
Similarly, picking a sufficient large <math>y</math> settles this case.
 +
 +
 +
Now, we extend our proof to general polynomials. If a polynomial <math>f(n)=a_0+a_1n+a_2n^2+...+a_xn^x</math> satisfies the conditions of the problem, then for any <math>m,y>0</math>:
 +
<cmath>f(m*10^y)=a_xm^x*10^{yx}+...+a_1m*10^y+a_0</cmath>
 +
Similarly, choosing <math>y</math> to be sufficiently large results in the terms not interfering with each other. If <math>f</math> contains any monomials that do not satisfy the conditions of the problem, then picking suitable <math>m</math> and sufficiently large <math>y</math> causes <math>f(m*10^y)</math> to not be in <math>K</math>. Thus, <math>f</math> is a linear polynomial of the form <math>ax+b</math> where <math>a</math> is 0 or a power of 10, and <math>b\in K</math>. It suffices to rule out those polynomials where <math>b>a</math>. If <math>b>a</math>, then since the digit of <math>b</math> corresponding to <math>a</math> is not 7, there must be a single-digit number <math>n</math> such that the digit of <math>f(n)</math> corresponding to <math>a</math> is 7. Therefore, we are done.
 +
 +
-wzs26843545602
  
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 06:11, 18 March 2023

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)=ax+b$ where $a$ is either 0 or a power of 10, and where $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 $b>a$. If $b>a$, 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 (Problems • Resources)
Preceded by
Problem 2 		Followed by
Problem 4
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2019_USAMO_Problems/Problem_3&oldid=191065"