Difference between revisions of "2016 USAJMO Problems/Problem 2"
Tigerzhang (talk | contribs) (→Solution 2) |
Tigerzhang (talk | contribs) (→Solution 2) |
||
Line 62: | Line 62: | ||
==Solution 2== | ==Solution 2== | ||
− | We divide the positive numbers into <math>10^{6}</math> groups, where the <math>n^{\text{th}}</math> group contains all the numbers <math>x</math> such that <math>{\log_{10}{ | + | We divide the positive numbers into <math>10^{6}</math> groups, where the <math>n^{\text{th}}</math> group contains all the numbers <math>x</math> such that <math>\frac{n-1}{10^{6}}\le\{\log_{10}x\}<\frac{n}{10^{6}}</math>, where |
{{MAA Notice}} | {{MAA Notice}} |
Revision as of 13:48, 29 June 2020
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
, where
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 |