I'll just give a hint: 142857 Of course there's much more to the problem but this gives a nice starting place. (Also http://www.artofproblemsolving.com/Forum/blog.php?u=35129&b=60360)

A slightly harder version is here: http://www.artofproblemsolving.com/blog/60360

math154 wrote:

pi37 wrote:

pi37 wrote: math154 wrote:

same gg

I let p be smallest prime greater than m+n, let x be the p-1-digit repetend of 1/p., and set c=x, Does that Work?

ucantbeatmario wrote: I let p be smallest prime greater than m+n, let x be the p-1-digit repetend of 1/p., and set c=x, Does that Work? Unfortunately not; For example, consider m,n = 3,7.

I also said that p does not equal 2,3,5 and 11 in my proof

dnkywin wrote:

Hmm also see http://www.artofproblemsolving.com/Forum/viewtopic.php?f=810&t=516644&

Here is an solution that works if k/m or k/n for some k is an ugly fraction with all 9 nonzero digits and which doesn't work otherwise, but I think it's hilarious that this idea can even be used The basic idea is that for sufficiently large d, $n(c_1+10^d c_2)$ has the (nonzero) digits combined from $nc_1$ and $nc_2$.

yes. The ith coordinate of P with respect to N would be the hypervolume of the simplex with all vertices of N and P instead of P(n c_i) divided by V_N

It's necessary that n_i=m_i. I don't think you need a contraction argument. In fact, I think you just need the fact that an infinite sequence of nested open sets has a common point. EDIT: actually it should be sequence of closed sets (in a compact space) oops darn

this retired old man feels youthful again

Here's a solution that doesn't use any "well known" facts

Okay so this is what I put on the USAMO verbatim:

Would this scrape at least one point?

That should get a 7 (the error in your lemma is trivial). Personally, though, I prefer the following (equivalent) wording in terms of mod $10^N - 1$ (for large $N$): math154 wrote:

In greater detail,

In terms of your proof, we're taking

Edit: I admit I did not check the details of robinpark's proof too carefully, but the proof has all the essential ingredients---small details (like we probably want $r$ to be sufficiently large) are missing, but in the end everything's going to be pretty much equivalent to my solution. So it's possible that if the graders care a lot about these details, the proof might be graded 0+ instead of 7-, but that would be unfair IMO.

I still dont understand how you know that for a given r and p we have $\frac{A(10^{r+p}-1)}{m10^r-n}$ AND $\frac{B(10^{r+p}-1)}{n10^r-m}$ are BOTH integers. As changing p to make the first number an integer, may render the second number to not be an integer. FURTHERMORE, when there is the claim that A and B may be scalled appropriately such that the desired equation is true, how is it obvious that they are still within the appropriate number of digits? With some further analysis you can note that for p and r large enough, we only need $A\le n$ and $B \le m$ in order to absorb the factors of 2s and 5s, but the scaling is still not obvious that it will retain $A$ and $B$ within the proper digit range.

math154 wrote: But if you want, you can just show (by contradiction) that infinitely many primes divide $10^k m - n$ for some $k\ge1$. Alternatively, you can show this by nuking it with Kobayashi's Theorem. I've been dying for an opportunity to use this on an olympiad/TST; looks like I missed my big chance

Maybe is a stupid question but I don't understand why if we know that 2 sets like $\{m\cdot 10^y-n\}$ and $\{n\cdot 10^y-m\}$ have infinite sets of primes they share an infinite sets of prime.

tenniskidperson3 wrote: Given positive 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 main idea is essentially how divisibility tests of $7, 9, 11$ work. Suppose $p>m+n$ is a prime number such that $p \mid 10^km-n$ for some $k \ge 1$. Now pick $N$ sufficiently big with $10^N \equiv 1 \pmod{p}$. Put $c=\tfrac{10^N-1}{p}$ and observe that $cm+cn<10^N-1$. Also $$10^N-1 \mid c(10^km-n).$$Now write $cm=\overline{a_1 \dots a_s}$ then $10^k(cm) \equiv \overline{a_1 \dots a_s \underbrace{0 \dots 0}_{k}}$ so after mod $10^N-1$ it breaks from the $N$th place and the left part switches towards the right, no carry overs occurring in the process (as $s<N$). Since $cn$ coincides mod $10^N-1$ we obtain an equal number of each non-zero digit. $\blacksquare$ Note. We can use Kobayashi's Theorem to pick a sufficiently large prime $p \mid 10^km-n$ for some $k$. However, it is also possible to give an elementary proof. Mimic the idea used here.

We will use the following claim. Given positive integers $m$ and $n$, then there exists $a,b,s$ such that $am-bn = s(10^k), an-bm = s(10^l)$ for every $k,l$ To prove the claim, pick $s=(m,n)(m^2-n^2)$. note that by Bezout, there must be a solution $(x,y)$ for $mx-ny=(m,n)$. Then $(a,b) = ((m^2-n^2)10^kx+tn,(m^2-n^2)10^ky+tm)$ is a solution for $am-bn = 10^k$. Plugging it into $an-bm$, we get $t = 10^k(nx-my)-10^l$. Then pick $c = 10^ua+b$ for $u,k,l$ sufficiently large. We get $cm = (10^ua+b)m = 10^u(s(10^k)+bn)+bm = s(10^{k+u})+bn(10^u)+bm$ and $cn = (10^ua+b)n = 10^u(bm+s(10^l))+bn = s(10^{l+u})+bm(10^{u})+bn$.

by $KOBAYASHI'S$ $TH.$ pick a large prime $p$ > $m+n$ . which divides $m.10^k - n$ . Note that the decimal representations of $10^k.m/p$ and $n/p$ , since there dif. is an integer [ so digits of block for $n/p$ also appears in the decimal representation of $10^k.m/p$ ] so take $c$ as the resulting integer at the block of decimal representation of $p$ . [ "Block" at the decimal representation ref. to the integers that are periodic ] EDIT : I see that possibly my sol. is same with Anant's sol. since his large $N$ may be compared with the length of the periodic part at the decimal representation of $p$ !!! The largeness then comes from the choice of $p$ .

Consider the sequence $\{10^i\cdot m+n\}$. By Kobayahsi's Theorem, this sequence contains infinitely many distinct prime divisors. So, consider a sufficiently large $i$, such that $p|10^i\cdot m+n$, where $p>m,n$. Now, consider the fractions $\frac{m}{p}$ and $\frac{n}{p}$. These two fractions both have repeating decimal expansions. However, note that $\left\{\frac{10^i\cdot m}{p}\right\}=\frac{n}{p}$ based on our construction, so the repeating part of $\frac{n}{p}$ is just a cyclic shift of $\frac{m}{p}$! Now, I claim that we can let $c$ be the number repeated in the decimal expansion of $\frac{1}{p}$. Indeed, $mc$ and $nc$ will just be cyclic shifts of each other if we include leading zeroes, so they will have the same number of occurrences of each non-zero digit.

william122 wrote: Consider the sequence $\{10^i\cdot m+n\}$. By Kobayahsi's Theorem, this sequence contains infinitely many distinct prime divisors. So, consider a sufficiently large $i$, such that $p|10^i\cdot m+n$, where $p>m,n$. Now, consider the fractions $\frac{m}{p}$ and $\frac{n}{p}$. These two fractions both have repeating decimal expansions. However, note that $\left\{\frac{10^i\cdot m}{p}\right\}=\frac{n}{p}$ based on our construction, so the repeating part of $\frac{n}{p}$ is just a cyclic shift of $\frac{m}{p}$! Now, I claim that we can let $c$ be the number repeated in the decimal expansion of $\frac{1}{p}$. Indeed, $mc$ and $nc$ will just be cyclic shifts of each other if we include leading zeroes, so they will have the same number of occurrences of each non-zero digit. I think that maybe you mean $\{10^i\cdot m-n\}$

This problem is well known see here http://en.wikipedia.org/wiki/Artin's_conjecture_on_primitive_roots#Proof_attempts

The main idea is to make $cm$ and $cn$ cyclic shifts of each other, as motivated by the example 142857. Specifically, suppose we have found integers $k\ge 1$ and $l>m,n$ such that \[\frac{10^km}{l} \equiv \frac{n}{l} \pmod{1}.\]This means that the repeating digits of $\frac{m}{l}$ and $\frac{n}{l}$ are cyclic shifts of each other by $k$ digits. Take $c$ to be the repetend of $\frac{1}{l}$ with leading zeros omitted, then $cm$ and $cn$ are cyclic shifts of each other with possible insertions of zeros. In particular each nonzero digit appears the same number of times. To find this $k$ and $l$, simply choose $k$ large enough such that $k>\max(v_2(n),v_5(n))$ and $l:=\frac{10^km-n}{2^{v_2(n)}5^{v_5(n)}} > \max(m,n)$.

The main motivation is the number 142857. Claim: There are infinitely many primes \(p\) such that the repeating decimal representations of \(m/p\) and \(n/p\) are cyclic shifts of each other. Proof. By Kobayashi theorem, infinitely many primes \(p\) divide some element of the sequence \(\{10^i\cdot n-m\}\). For such \(p\), \[10^i\equiv\frac mn\pmod p\implies\frac mp=\left\{10^i\cdot\frac np\right\}.\]\(\blacksquare\) Then it suffices to take \(p\) large enough and consider \(c\) one period of the repeating decimal representation of \(1/p\); rigorously, \[c=\frac{10^{\operatorname{ord}_p(10)}-1}p\in\mathbb Z.\]

Interestingly I didn't even think of 142857 when solving this. I, in fact, was motivated by this video.

Then $c=\frac{10^{\phi(10m-n)}-1}{10m-n}$ works: Actually, $cn$ is just $cm$ with the the first digit moved to the last digit. $cm$ is between $(10^{\phi(10m-n)}-1)/10m\cdot m=999\cdots9.9$ and $(10^{\phi(10m-n)}-1)/9m\cdot m=111\cdots1$, so the first digit of $cm$ is 1, at place value $10^{\phi(10m-n)-1}$. Then $cn=10cm-(10^{\phi(10m-n)}-1)$, which does what was claimed. Edit: Remark: Any $c'=ac$ where the first digit of $c'm$ is $a$ works. The WLOGs allow us to just consider a subset of when $a=1$.

This solution is brought to you by the number $142857$. The result is immediate for $m=n$ so suppose $m>n$ WLOG. By Kobayashi, there exists a positive integer $k$ and a prime $p>TREE(m+n+2+5)$ for which $p\mid 10^km-n$. Let $c$ be such that $1/p=0.\overline{c}$ where $\overline{c}$ indicates $c$ concatenated ad infinitum and $c$ is minimal. Then we claim that $c$ is the desired choice of $c$. Let $\ell$ be the period of $1/p$. Then $cm$ consists of the first $\ell$ digits of the decimal expansion of $m/p$ after the period, $cn$ consists of the first $\ell$ digits of the decimal expansion of $n/p$ after the period, so because $(10^km-n)/p$ is an integer, the digits of $cn$ are a cyclic shift of the digits of $cm$ with $0$s added as necessary, implying the desired.

Most of the proof is looking for the prime number. But do we really need prime? It looks like the prime number does nothing in the proof. For example, for $m=7, n=13$, $10m-n=57$. Then \begin{align*} 7/57 = 0.122807017543859649...\\ 13/57= 0.228070175438596491...\end{align*}So Letting $c= ({10^{\phi(57)}-1}) / 57$ is enough for the $(7,13)$.

Claim: For all positive integers $m$ and $n$, there exist infinitely many primes $p$ so that the repeating decimal representations of $\frac{m}{p}$ and $\frac{n}{p}$ are cyclic shifts of each other. Proof: Let $p$ satisfy $p$ is much greater than $\max(m,n)$. We want to show that there exists a positive integer $k$ so that $\frac{10^k m}{p}-\frac{n}{p}=\frac{10^k m-n}{p}\in \mathbb{Z}\iff p|10^k m -n$, which is true by Kobayashi's Theorem. We now have $\left\{\frac{10^k m}{p}\right\}=\frac{n}{p}$, which implies the repeating decimal representation of $\frac{n}{p}$ is a cyclic shift of $\frac{m}{p}$. Now for sufficiently large such $p$, let $\frac{1}{p}=0.\overline{c}$, where $c$ is minimal. Since $p$ is much larger than $m$ or $n$, we have $\frac{m}{p}=0.\overline{cm}$, where $cm$ denotes $c\cdot m$. For example, if $c=142857$ and $m=2$, then $\frac{m}{p}=0.\overline{285714}$. Similarly, $\frac{n}{p}=0.\overline{cn}$. Thus, $0.\overline{cm}$ and $0.\overline{cn}$ are cyclic shifts of each other, which implies $cm$ and $cn$ have the same occurrences of each digit except for $0$ (since a positive integer can't have first digit $0$).

megarnie wrote: Claim: For all positive integers $m$ and $n$, there exist infinitely many primes $p$ so that the repeating decimal representations of $\frac{m}{p}$ and $\frac{n}{p}$ are cyclic shifts of each other. Proof: Let $p$ satisfy $p$ is much greater than $\max(m,n)$. We want to show that there exists a positive integer $k$ so that $\frac{10^k m}{p}-\frac{n}{p}=\frac{10^k m-n}{p}\in \mathbb{Z}\iff p|10^k m -n$, which is true by Kobayashi's Theorem. We now have $\left\{\frac{10^k m}{p}\right\}=\frac{n}{p}$, which implies the repeating decimal representation of $\frac{n}{p}$ is a cyclic shift of $\frac{m}{p}$. Now for sufficiently large such $p$, let $\frac{1}{p}=0.\overline{c}$, where $c$ is minimal. Since $p$ is much larger than $m$ or $n$, we have $\frac{m}{p}=0.\overline{cm}$, where $cm$ denotes $c\cdot m$. For example, if $c=142857$ and $m=2$, then $\frac{m}{p}=0.\overline{285714}$. Similarly, $\frac{n}{p}=0.\overline{cn}$. Thus, $0.\overline{cm}$ and $0.\overline{cn}$ are cyclic shifts of each other, which implies $cm$ and $cn$ have the same occurrences of each digit except for $0$ (since a positive integer can't have first digit $0$). I still cannot believe you got a 108 on the 10a

pi271828 wrote: megarnie wrote: Claim: For all positive integers $m$ and $n$, there exist infinitely many primes $p$ so that the repeating decimal representations of $\frac{m}{p}$ and $\frac{n}{p}$ are cyclic shifts of each other. Proof: Let $p$ satisfy $p$ is much greater than $\max(m,n)$. We want to show that there exists a positive integer $k$ so that $\frac{10^k m}{p}-\frac{n}{p}=\frac{10^k m-n}{p}\in \mathbb{Z}\iff p|10^k m -n$, which is true by Kobayashi's Theorem. We now have $\left\{\frac{10^k m}{p}\right\}=\frac{n}{p}$, which implies the repeating decimal representation of $\frac{n}{p}$ is a cyclic shift of $\frac{m}{p}$. Now for sufficiently large such $p$, let $\frac{1}{p}=0.\overline{c}$, where $c$ is minimal. Since $p$ is much larger than $m$ or $n$, we have $\frac{m}{p}=0.\overline{cm}$, where $cm$ denotes $c\cdot m$. For example, if $c=142857$ and $m=2$, then $\frac{m}{p}=0.\overline{285714}$. Similarly, $\frac{n}{p}=0.\overline{cn}$. Thus, $0.\overline{cm}$ and $0.\overline{cn}$ are cyclic shifts of each other, which implies $cm$ and $cn$ have the same occurrences of each digit except for $0$ (since a positive integer can't have first digit $0$). I still cannot believe you got a 108 on the 10a I am really bad at timed contests (and also geo).

megarnie wrote: pi271828 wrote: megarnie wrote: Claim: For all positive integers $m$ and $n$, there exist infinitely many primes $p$ so that the repeating decimal representations of $\frac{m}{p}$ and $\frac{n}{p}$ are cyclic shifts of each other. Proof: Let $p$ satisfy $p$ is much greater than $\max(m,n)$. We want to show that there exists a positive integer $k$ so that $\frac{10^k m}{p}-\frac{n}{p}=\frac{10^k m-n}{p}\in \mathbb{Z}\iff p|10^k m -n$, which is true by Kobayashi's Theorem. We now have $\left\{\frac{10^k m}{p}\right\}=\frac{n}{p}$, which implies the repeating decimal representation of $\frac{n}{p}$ is a cyclic shift of $\frac{m}{p}$. Now for sufficiently large such $p$, let $\frac{1}{p}=0.\overline{c}$, where $c$ is minimal. Since $p$ is much larger than $m$ or $n$, we have $\frac{m}{p}=0.\overline{cm}$, where $cm$ denotes $c\cdot m$. For example, if $c=142857$ and $m=2$, then $\frac{m}{p}=0.\overline{285714}$. Similarly, $\frac{n}{p}=0.\overline{cn}$. Thus, $0.\overline{cm}$ and $0.\overline{cn}$ are cyclic shifts of each other, which implies $cm$ and $cn$ have the same occurrences of each digit except for $0$ (since a positive integer can't have first digit $0$). I still cannot believe you got a 108 on the 10a I am really bad at timed contests (and also geo). I just suck at doing contests in general

Yeah same I am bad under pressure.

EmptySet wrote: The idea is to introduce a third number, k. Then we can choose a constant c such that cm that has m's digits followed by n's digits followed by k's digits, and cn that has n's digits followed by k's digits followed by m's digits. Just curious, what is the motivation for this idea? This seems random to me?

By Kobayashi, pick a massive prime $p \gg m,n$ such that $p \mid 10^kn-m$ for some positive integer $k$. Then consider $c=\tfrac{10^{p-1}-1}{p}$. We have $$cm \equiv 10^kcn \pmod{10^{p-1}-1} \iff m \equiv 10^kn \pmod{p},$$which is true. Furthermore, since $cm$ and $cn$ are both less than $10^{p-1}-1$, it follows that (after padding with leading $0$s as necessary) $cm$ and $cn$ are cyclic shifts of each other, since multiplying a number by $10$ and then taking its remainder upon division by $10^{p-1}-1$ corresponds to a single cyclic shift leftwards. Therefore, without leading zeroes, $cm$ and $cn$ will have the same number of occurrences of each nonzero digit in base $10$. $\blacksquare$

This solution is sponsered by $142857$. Shoutout to $142857$ for being the main motivator in this writeup Consider a prime $p$ that is massive in comparison to $m$ and $n$ that also divides some term in $\{10^in-m\}$. This clearly exists by Kobayashi, and then we get \[m \equiv 10^in \pmod{p} \implies \frac{m}{p} = \left \{10^i \cdot \frac{n}{p} \right \}.\] This means that $\tfrac{m}{p}$ and $\tfrac{n}{p}$ are cyclic shifts of each other. Kobayashi states that infinitely many $p$ exist. Hence, by letting $c$ by the period of $\tfrac{1}{p}$, we get infinitely many $c$ as well. $\square$ pls don't be wrong :pray: