2016 USAJMO Problems/Problem 2: Difference between revisions
Tigerzhang (talk | contribs) |
|||
| Line 60: | Line 60: | ||
From this, Euler's Theorem comes to mind and we see that if <math>n-20 = \varphi\left(2^{20}\right)</math>, the equality is satisfied. Thus, we get that <math>n = 20 + 2^{19}</math>, which is less than <math>10^6</math>, and we should be done. However, this requires slightly more formalization, and can be proven directly more easily if <math>n = 20+2^{19}</math> is known or suspected. | From this, Euler's Theorem comes to mind and we see that if <math>n-20 = \varphi\left(2^{20}\right)</math>, the equality is satisfied. Thus, we get that <math>n = 20 + 2^{19}</math>, which is less than <math>10^6</math>, and we should be done. However, this requires slightly more formalization, and can be proven directly more easily if <math>n = 20+2^{19}</math> is known or suspected. | ||
==Solution 2== | |||
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:39, 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
![\[5^n \mod 10^k < 10^{k-6}\]](http://latex.artofproblemsolving.com/5/1/f/51fd401a20dd2fdc46bdb060ef8e5d2f8d6f161f.png)
We will prove that 
satisfies this, thus proving the problem statement (since 
).
We want
![\[5^{20+2^{19}} \mod 10^{20}\]](http://latex.artofproblemsolving.com/e/1/f/e1fb33e88db7fa8448933afffd956d9c0dca8fe8.png)
![\[5^{20} \left(5^{2^{19}} \mod 2^{20}\right)\]](http://latex.artofproblemsolving.com/f/a/6/fa6aeb8cc91d43c71927dd62949fc88140a23a07.png)
![\[5^{20} \left(5^{\varphi \left(2^{20}\right)} \mod 2^{20}\right)\]](http://latex.artofproblemsolving.com/e/0/e/e0e5c9485c3c6141b4de439cecbfb6a51241138c.png)
(
is the Euler Totient Function.) By Euler's Theorem, since gcd
= 1,
![\[5^{\varphi \left(2^{20}\right)} \mod 2^{20} = 1\]](http://latex.artofproblemsolving.com/2/3/5/2356c0a4b971bf5c441d824c44f24858f72dfaff.png)
so
![\[5^{20} \left(5^{\varphi \left(2^{20}\right)} \mod 2^{20}\right) = 5^{20}\]](http://latex.artofproblemsolving.com/0/8/5/085d863d3fb784817f5d9fc1e12d87aa189e88e4.png)
Since 
, so
for 
and 
, and thus the problem statement has been proven. 
Motivation for Solution
Modifying our necessary and sufficient inequality, we get:
![\[5^k \left(5^{n-k} \mod 2^k\right) < 10^{k-6}\]](http://latex.artofproblemsolving.com/3/f/c/3fcc2a2170799f68cf10c8fffd70c540c29926ad.png)
![\[5^{n-k} \mod 2^k < \frac{2^{k-6}}{5^6}\]](http://latex.artofproblemsolving.com/7/8/6/7865ca3755556b9de468d2fd9153b16e3a744a4b.png)
Since gcd
if 
(which is obviously true) and 
which is also true given that 
, we need the RHS to be greater than :
![\[\frac{2^{k-6}}{5^6} > 1\]](http://latex.artofproblemsolving.com/2/1/2/21288ecdd861b9bc60ea16310261618a8d93c6bd.png)
![\[2^{k-6} > 5^6\]](http://latex.artofproblemsolving.com/e/0/d/e0dea000d69f61209866be85923c8d4c2ef79d20.png)
![\[2^k > 10^6\]](http://latex.artofproblemsolving.com/9/3/7/937416acd0e5df5818974dd1cddd563d6a3baa68.png)
The first that satisfies this inequality is , so we let :
![\[5^{n-20} \mod 2^{20} < \frac{2^{14}}{5^6}\]](http://latex.artofproblemsolving.com/9/b/1/9b1bd3d90b9c94e2f4f89b147f7dc83a5a7da918.png)
![\[5^{n-20} \mod 2^{20} \leq 1\]](http://latex.artofproblemsolving.com/1/f/6/1f61d85df3f0e18a3db963b02e97b78dbfc38c4b.png)
![\[5^{n-20} \mod 2^{20} = 1\]](http://latex.artofproblemsolving.com/f/a/c/facbe61a5028bb9ee5c2e439ad5b59a55150aff1.png)
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.
These problems are copyrighted © by the Mathematical Association of America. 
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 | ||
