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:
First Solution: For a given positive integer , write , where 1. For large enough values of the number of times 2 and 5 divide the left-hand side is at most the number of times they divide , hence by choosing large we can make arbitrarily large. Choose so that is larger than either or .
Since is relatively prime to 10 there is a smallest exponent for which . Thus is the number of digits in the repeating portion of the decimal expansion for . More precisely, if we write , then the repeating block is the -digit decimal representation of , obtained by prepending extra initial zeros to as necessary. Since is larger than or , the decimal expansions of and will consist of repeated -digit representations of and , respectively. Rewriting the identity in the first line as
we see that the decimal expansion of is obtained from that of by shifting the decimal to the right places and removing the integer part. Thus the -digit representations of and are cyclic shifts of one another. In particular, they have the same number of occurrences of each nonzero digit. (Because they may have different numbers of leading zeros as -digit numbers, the number of zeros in their decimal expansions may differ.)
This problem and solution were suggested by Richard Stong.
Second Solution: Suppose without loss of generality that . Note that if the desired conclusion holds for the pair for some , then it also holds for . Write for some relatively prime to 10 , and note that it suffices to show the\
desired statement for the pair . Further, because ends with a string of trailing 's it suffices to show the desired for the pair , where . Thus, from now on we assume that .
For such a pair , we see that , so we may find some and some so that , which implies that . We observe that , hence for some which satisfies . Substituting in, we find that
which implies that the non-zero digits of are exactly those of with an additional 1 . But the non-zero digits of are those of with an additional 1 , so the non-zero digits of cn and coincide, as needed.
This solution was suggested by Xiaodong Zhou.
The problems on this page are the property of the MAA's American Mathematics Competitions