Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This is currently unsolved in the AoPS site, the problem says:

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.

I couldn't even give it a try, since I find this problem quite rare, but still very interesting. When they mention "non-zero digits" it makes me think that we may exploit this feature and direct all the colateral effects of multiplication to those zeroes. After that, I don't have a clear idea on what to do.

share|improve this question
    
I was wondering what $c$ is for $m=1$, $n=2$. –  Lord Soth Jul 20 '13 at 2:29
2  
Found it! $c = 125874$ for $m=1, n=2$. –  Lord Soth Jul 20 '13 at 2:39
    
also did a quick search in (codepad.org/LFWobgAN), surprised it wasn't in the first thousand. –  chubakueno Jul 20 '13 at 2:41
1  
Here is some Python code that can be used to find the $c$ values, in case it can help anyone. –  arshajii Jul 20 '13 at 2:51
4  
You can find the solutions to the 2013 USAMO here: web.archive.org/web/20130606075948/http://amc.maa.org/usamo/… –  lyj Jul 20 '13 at 5:06

1 Answer 1

up vote 3 down vote accepted

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.$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.