2013 USAMO problem 5

Solution 1:

As I mentioned in the comments, you can find the official solution here, though I think it isn't too illuminating. Also, I'm surprised that there's no discussion thread on AoPS for this problem... Anyway:

As noted, when $m=1, n=2,$ the solutions to $c$ seem to always produce $mc$ and $nc$ that are cyclic shifts of one another, so it's natural to try to construct such a $c$ for all $m, n.$

Let's start with something easy. Take $A$ and $B$ to be positive integers, and suppose $B$ has the same digits as $A,$ except shifted by one to the left (so the first digit of $A$ is not the last digit of $B$). How can we think of $B?$ Well, the usual way of approaching problems concerning digits is to look at the decimal expansion and considering differences. In this case, note that shifting every digit of $A$ to the left is the "same" as multiplying by $10.$ Now, it should be clear that $10A - B$ is in fact $(10^{n} - 1)\cdot d,$ where $n$ is the number of digits in $A$ and $B,$ and $1\le d\le 9.$

In general, it is true that shifting by $s$ digits to the left implies $10^{s}A - B$ is divisible by $10^{n}-1,$ but we don't need this to solve our problem. What we're searching for is a way to force $cm$ and $cn$ to be cyclic shifts of one another. And the natural conjecture is the converse of our statement above. Namely, if $10^{n}-1\mid 10^{s}A-B$ for some $s,$ then $B$ is equal to $A$ shifted by $s$ digits to the left. Let's prove this.

Claim: Let $A$ and $B$ be positive integers such that the larger of the two has $n$ digits. If $10^{n}-1\mid 10^{s}A-B$ for some $s \ge 0,$ then $B$ is equal to the cyclic shift of $A$ by $s$ digits (to the left).

Remark: We note that we can assume $s < n$ since $10^{n+s}A - 10^{s} A$ is automatically divisible by $10^{n}-1.$

Proof: Let $A = 10^{n-1}a_{n-1} + \ldots + a_0$ and suppose $10^{s}A - 10^{n}d + d = B$ for some $s > 0$ and $d > 0$ ($s = 0$ is trivial). Then $$10^{s}A - 10^{n}d+d = 10^{n+s-1}a_{n-1} + \ldots + 10^{n}a_{n-s} + \ldots + 10^{s}a_0 - 10^{n}d + d = B < 10^{n}-1.$$

Now, observe that if we can produce $d$ such that the middle expression is between $0$ and $10^{n}-1,$ then it must be $B$ by the division algorithm. Taking $d = 10^{s-1}a_{n-1} + \ldots + a_{n-s}$ yields $$10^{s}A - (10^{n}-1)d = 10^{n-1}a_{n-s-1} + \ldots + 10^{s}a_0 + 10^{s-1}a_{n-1} + \ldots + a_{n-s},$$ which is necessarily less than $10^{n}.$ Hence $B$ is obtained by shifting the digits of $A$ to the left by $s.$

From here, we want to find $c$ and $s$ such that $10^{s}cm - cn$ is divisible by $10^{N}-1,$ where $10^{N}-1 > cm, cn.$ Equivalently, we need $c(10^{s}m - n)$ to be divisible by $10^{N}-1.$ The easiest way to satisfy all the conditions is to make $10^{s}m-n$ divide by $10^{N}-1$ for some large $N,$ and then we can choose $c$ accordingly. Obviously, there is the caveat that $n$ may have a common factor with $10,$ but it's not difficult to remove this possibility. Hence, let $(n,10) = 1.$ Then take $s$ large enough so that $10^{s}m-n > m,n.$ Since $10^{s}m-n$ has no common factors with $10,$ there exists $N$ such that $10^{N} - 1$ is divisible by it (for example, $\phi(10^{s}m-n)$ works). Now just take $c = \dfrac{10^{N}-1}{10^{s}m-n}$ to finish. Note that $cm, cn < 10^{N}-1$ by assumption on $10^{s}m-n.$