2016 USAJMO Problems/Problem 2
Problem
Prove that there exists a positive integer such that
has six consecutive zeros in its decimal representation.
Solution
Let digit of a number be the units digit, digit
be the tens digit, and so on. Let the 6 consecutive zeroes be at digits
through digit
. The criterion is then obviously equivalent to
We will prove that satisfies this, thus proving the problem statement (since
).
We want
( is the Euler Totient Function.) By Euler's Theorem, since gcd
= 1,
so
Since , so
for and
, and thus the problem statement has been proven.
Motivation for Solution
Modifying our necessary and sufficient inequality, we get:
Since gcd if
(which is obviously true) and
which is also true given that
, we need the RHS to be greater than
:
The first that satisfies this inequality is
, so we let
:
From this, Euler's Theorem comes to mind and we see that if , the equality is satisfied. Thus, we get that
, which is less than
, and we should be done. However, this requires slightly more formalization, and can be proven directly more easily if
is known or suspected.
Solution 2
We divide the positive numbers into groups.
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.
See also
2016 USAJMO (Problems • Resources) | ||
Preceded by Problem 1 |
Followed by Problem 3 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAJMO Problems and Solutions |