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, where the group contains all the numbers such that
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 |