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.
Solutions — 3
Solution 1
Solution 1 (By Richard Stong). For a given positive integer , write , where . 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.
Solution 2 (By Zhou Xiaodong). Suppose without loss of generality that . Note that if the desired 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 0's it suffices to show the desired for the pair , where . Thus, it suffices to consider with .
For such a pair , we see that , so we may find some and some so that
, which after rearranging implies that
In addition, we see that , hence cm has exactly k digits and cn has l digits for l k. If and are the decimal expansions of cm and cn (where some of the leading digits of cn may be 0), then the above equality yields the equality of decimal expansions
We conclude that and for , so each non-zero digit appears among and the same number of times, hence appears in cn and cm the same number of times.
Solution 2
Since is relatively prime to 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.
Solution 3
Suppose without loss of generality that . Note that if the desired holds for the pair for some , then it also holds for . Write for some relatively prime to , and note that it suffices to show the desired statement for the pair . Further, because ends with a string of trailing 0's it suffices to show the desired for the pair , where . Thus, it suffices to consider with .
For such a pair , we see that , so we may find some and some so that
, which after rearranging implies that
In addition, we see that , hence has exactly digits and has digits for . If and are the decimal expansions of and (where some of the leading digits of may be ), then the above equality yields the equality of decimal expansions
We conclude that and for , so each non-zero digit appears among and the same number of times, hence appears in and the same number of times.