2013 USAMO Problems/Problem 5
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.