2013 USAMO Problems/Problem 5
Given postive 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. The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.
This solution is adopted from the official solution. Both the problem and the solution were suggested by Richard Stong.
WLOG, 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 .