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