Difference between revisions of "2019 USAMO Problems/Problem 3"
(→Solution) |
(→Solution) |
||
Line 3: | Line 3: | ||
==Solution== | ==Solution== | ||
− | I claim the only such polynomials are of the form <math>f(n)= | + | I claim the only such polynomials are of the form <math>f(n)=k</math> where <math>k\in K</math>, or <math>f(n)=an+b</math> where <math>a</math> is a power of 10, <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 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. | ||
Line 19: | Line 19: | ||
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>: | 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> | <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> | + | 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>a>0</math> and <math>b>a</math>. If this is the case |
+ | |||
+ | , 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 | -wzs26843545602 |
Revision as of 15:08, 18 March 2023
Problem
Let be the set of all positive integers that do not contain the digit in their base- representation. Find all polynomials with nonnegative integer coefficients such that whenever .
Solution
I claim the only such polynomials are of the form where , or where is a power of 10, , and . Obviously, these polynomials satisfy the conditions. We now prove that no other polynomial works. That is, we prove that for any other polynomial with nonnegative coefficients, there is some such that .
We first prove the result for monomials, polynomials in which only one coefficient is nonzero. This is obvious for constant polynomials . The next simplest case is with not a power of 10, and hence is irrational. By Dirichlet's approximation theorem, the set of multiples of is dense , and thus contains an element with fractional part in the interval . In other words, there is a power of whose decimal expansion starts with a 7. Let be the smallest power of that is not in . Obviously, , so letting completes the proof of this part.
We have now proven that for any that is not a power of 10, there is some such that . We proceed to the case where for . This splits into 2 cases. If is not a power of 10, then pick such that . For any , we have
If we choose 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 .
On the other hand, if is a power of 10, then and are both powers of 10, and . Obviously, is not a power of 10. By the previous step, which establishes the result for , we can pick such that . Then, for any , Similarly, picking a sufficient large settles this case.
Now, we extend our proof to general polynomials. If a polynomial satisfies the conditions of the problem, then for any :
Similarly, choosing to be sufficiently large results in the terms not interfering with each other. If contains any monomials that do not satisfy the conditions of the problem, then picking suitable and sufficiently large causes to not be in . Thus, is a linear polynomial of the form where is 0 or a power of 10, and . It suffices to rule out those polynomials where and . If this is the case
, then since the digit of corresponding to is not 7, there must be a single-digit number such that the digit of corresponding to is 7. Therefore, we are done.
-wzs26843545602
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.
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 |