Difference between revisions of "2016 USAJMO Problems/Problem 2"
Tigerzhang (talk | contribs) (→Motivation for Solution) |
Tigerzhang (talk | contribs) (→Solution 2) |
||
Line 63: | Line 63: | ||
We divide the positive numbers into <math>999999</math> groups. | We divide the positive numbers into <math>999999</math> groups. | ||
+ | |||
{{MAA Notice}} | {{MAA Notice}} | ||
==See also== | ==See also== | ||
{{USAJMO newbox|year=2016|num-b=1|num-a=3}} | {{USAJMO newbox|year=2016|num-b=1|num-a=3}} |
Revision as of 13:40, 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.
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 |