2019 USAMO Problems/Problem 3
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 .
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.
|2019 USAMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5 • 6|
|All USAMO Problems and Solutions|