Difference between revisions of "2013 USAMO Problems/Problem 5"
Alphacapture (talk | contribs) (→Solution: Added Solution 2) |
|||
(7 intermediate revisions by 4 users not shown) | |||
Line 1: | Line 1: | ||
− | Given | + | == Problem == |
+ | Given positive integers <math>m</math> and <math>n</math>, prove that there is a positive integer <math>c</math> such that the numbers <math>cm</math> and <math>cn</math> have the same number of occurrences of each non-zero digit when written in base ten. | ||
+ | |||
+ | == Solution 1 == | ||
+ | This solution is adopted from the [http://web.archive.org/web/20130606075948/http://amc.maa.org/usamo/2013/2013USAMO_Day1_Day2_Final_S.pdf official solution]. Both the problem and the solution were suggested by Richard Stong. | ||
+ | |||
+ | Without Loss of Generality, suppose <math>m \geq n \geq 1</math>. By prime factorization of <math>n</math>, we can find a positive integer <math>c_1</math> such that <math>c_1n=10^s n_1</math> where <math>n_1</math> is relatively prime to <math>10</math>. If a positive <math>k</math> is larger than <math>s</math>, then <math>(10^k c_1 m - c_1 n)= 10^s t</math>, where <math>t=10^{k-s} c_1m-n_1>0</math> is always relatively prime to <math>10</math>. | ||
+ | |||
+ | Choose a <math>k</math> large enough so that <math>t</math> is larger than <math>c_1m</math>. We can find an integer <math>b\geq 1</math> such that <math>10^b-1</math> is divisible by <math>t</math>, and also larger than <math>10c_1m</math>. For example, let <math>b=\varphi(t)</math> and use Euler's theorem. Now, let <math>c_2=(10^b-1)/t</math>, and <math>c=c_1c_2</math>. We claim that <math>c</math> is the desired number. | ||
+ | |||
+ | Indeed, since both <math>c_1m</math> and <math>n_1</math> are less than <math>t</math>, we see that the decimal expansion of both the fraction <math>(c_1m)/t = (cm)/(c_2t) = (cm)/(10^b-1)</math> and <math>n_1/t=(c_2n_1)/(10^b-1)</math> are repeated in <math>b</math>-digit. And we also see that <math> 10^k (c_1m)/t = (t+c_1n)/t= 1+10^s (n_1/t)</math>, therefore the two repeated <math>b</math>-digit expansions are cyclic shift of one another. | ||
+ | |||
+ | This proves that <math>cm</math> and <math>c_2n_1</math> have the same number of occurrences of non-zero digits. Furthermore, <math>cn = c_2c_1n=10^s c_2n_1</math> also have the same number of occurrences of non-zero digits with <math>c_2n_1</math>. | ||
+ | |||
+ | == Solution 2 == | ||
+ | This is a rephrasing of the above solution. | ||
+ | |||
+ | It is enough to solve the problem when <math>m,n</math> are replaced by <math>km,kn</math> for any positive integer <math>k</math>. In particular, by taking <math>k=2^a5^b</math> for appropriate values of <math>a,b</math>, we may assume <math>n=10^sn_1</math> where <math>n_1</math> is relatively prime to 10. | ||
+ | |||
+ | Furthermore, adding or removing trailing zeros from <math>m</math> and <math>n</math> doesn't affect the claim, so we may further assume <math>\gcd(n,10)=1</math> and that <math>m</math> has a xillion trailing zeros (enough to make <math>m</math> way bigger than <math>n</math>, and also so that <math>m</math> has at least one trailing zero). | ||
+ | |||
+ | For clarity of exposition, we will also multiply <math>m,n</math> by a small number to make the units digit of <math>n</math> be <math>1</math> (though this is not necessary for the solution to work). | ||
+ | |||
+ | The point is that, for any positive integer <math>X</math>, most nonzero digits appear the same number of times in <math>X</math> and <math>X+999\dots999</math> if there are enough <math>9</math>s; In particular, if the units digits of <math>X</math> is <math>1</math>, then all nonzero digits appear the same number of times as long as there are at least as many <math>9</math>s as digits in <math>X</math>. | ||
+ | |||
+ | So we will pick <math>c</math> to satisfy: | ||
+ | * <math>mc=nc+999\dots999</math> where the number of <math>9</math>s is more than the number of digits of <math>nc</math> | ||
+ | * The units digit of <math>nc</math> is <math>1</math>. | ||
+ | |||
+ | Because we made the units of <math>n</math> to be <math>1</math>, the second condition is equivalent to making the units digit of <math>c</math> to be <math>1</math>. | ||
+ | |||
+ | The first condition is equivalent to <math>(m-n)c=999\dots999</math>. Because <math>m</math> has at least one trailing 0, the units digit of <math>m-n</math> is 9, so <math>\gcd(m-n,10)=1</math> and there is some <math>c</math> so that <math>(m-n)c=999\dots999</math>, and the units digit of <math>c</math> must be <math>1</math> which agrees with the other condition. | ||
+ | |||
+ | Finally, as <math>m\gg n, (m-n)c\approx mc\gg nc</math> so it is possible to make the number of <math>9</math>s more than the number of digits in <math>nc</math>. | ||
+ | |||
+ | |||
+ | {{MAA Notice}} |
Latest revision as of 23:31, 6 September 2023
Problem
Given positive integers and , prove that there is a positive integer such that the numbers and have the same number of occurrences of each non-zero digit when written in base ten.
Solution 1
This solution is adopted from the official solution. Both the problem and the solution were suggested by Richard Stong.
Without Loss of Generality, suppose . By prime factorization of , we can find a positive integer such that where is relatively prime to . If a positive is larger than , then , where is always relatively prime to .
Choose a large enough so that is larger than . We can find an integer such that is divisible by , and also larger than . For example, let and use Euler's theorem. Now, let , and . We claim that is the desired number.
Indeed, since both and are less than , we see that the decimal expansion of both the fraction and are repeated in -digit. And we also see that , therefore the two repeated -digit expansions are cyclic shift of one another.
This proves that and have the same number of occurrences of non-zero digits. Furthermore, also have the same number of occurrences of non-zero digits with .
Solution 2
This is a rephrasing of the above solution.
It is enough to solve the problem when are replaced by for any positive integer . In particular, by taking for appropriate values of , we may assume where is relatively prime to 10.
Furthermore, adding or removing trailing zeros from and doesn't affect the claim, so we may further assume and that has a xillion trailing zeros (enough to make way bigger than , and also so that has at least one trailing zero).
For clarity of exposition, we will also multiply by a small number to make the units digit of be (though this is not necessary for the solution to work).
The point is that, for any positive integer , most nonzero digits appear the same number of times in and if there are enough s; In particular, if the units digits of is , then all nonzero digits appear the same number of times as long as there are at least as many s as digits in .
So we will pick to satisfy:
- where the number of s is more than the number of digits of
- The units digit of is .
Because we made the units of to be , the second condition is equivalent to making the units digit of to be .
The first condition is equivalent to . Because has at least one trailing 0, the units digit of is 9, so and there is some so that , and the units digit of must be which agrees with the other condition.
Finally, as so it is possible to make the number of s more than the number of digits in .
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.