2019 USAMO Problems/Problem 3
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
is either 0 or a power of 10, and where
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
. If
, 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 |