2013 USAMO Problems/Problem 5

Given postive integers $m$ and $n$ , prove that there is a positive integer $c$ such that the numbers $cm$ and $cn$ have the same number of occurrences of each non-zero digit when written in base ten. These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. Error creating thumbnail: File missing

Solution

This solution is adopted from the official solution. Both the problem and the solution were suggested by Richard Stong.

WLOG, suppose $m \geq n \geq 1$ . By prime factorization of $n$ , we can find a positive integer $c_1$ such that $c_1n=10^s n_1$ where $n_1$ is relatively prime to $10$ . If a positive $k$ is larger than $s$ , then $(10^k c_1 m - c_1 n)= 10^s t$ , where $t=10^{k-s} c_1m-n_1>0$ is always relatively prime to $10$ .

Choose a $k$ large enough so that $t$ is larger than $c_1m$ . We can find an integer $b\geq 1$ such that $10^b-1$ is divisible by $t$ , and also larger than $10c_1m$ . For example, let $b=\varphi(t)$ and use Euler's theorem. Now, let $c_2=(10^b-1)/t$ , and $c=c_1c_2$ . We claim that $c$ is the desired number.

Indeed, since both $c_1m$ and $n_1$ are less than $t$ , we see that the decimal expansion of both the fraction $(c_1m)/t = (cm)/(c_2t) = (cm)/(10^b-1)$ and $n_1/t=(c_2n_1)/(10^b-1)$ are repeated in $b$ -digit. And we also see that $10^k (c_1m)/t = (t+c_1n)/t= 1+10^s (n_1/t)$ , therefore the two repeated $b$ -digit expansions are cyclic shift of one another.

This proves that $cm$ and $c_2n_1$ have the same number of occurrences of non-zero digits. Furthermore, $cn = c_2c_1n=10^s c_2n_1$ also have the same number of occurrences of non-zero digits with $c_2n_1$ .

Page

Toolbox

Search

2013 USAMO Problems/Problem 5

Solution