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. The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.

Solution

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

Without Loss of Generality, 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