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.
Problem
Source: 2013 USAMO Problem 5
Tags: modular arithmetic, probability, function, ratio, AMC, USA(J)MO, number theory
02.05.2013 01:09
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)
02.05.2013 01:14
A slightly harder version is here: http://www.artofproblemsolving.com/blog/60360
02.05.2013 01:16
math154 wrote:
02.05.2013 01:20
pi37 wrote:
02.05.2013 01:21
pi37 wrote: math154 wrote:
same gg
02.05.2013 01:33
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?
02.05.2013 01:35
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.
02.05.2013 01:38
I also said that p does not equal 2,3,5 and 11 in my proof
02.05.2013 01:53
dnkywin wrote:
02.05.2013 01:58
Hmm also see http://www.artofproblemsolving.com/Forum/viewtopic.php?f=810&t=516644&
02.05.2013 02:24
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$.
02.05.2013 04:22
02.05.2013 04:29
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
02.05.2013 05:21
02.05.2013 05:37
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
02.05.2013 07:09
this retired old man feels youthful again
02.05.2013 08:05
Here's a solution that doesn't use any "well known" facts
03.05.2013 22:44
Okay so this is what I put on the USAMO verbatim:
Would this scrape at least one point?
03.05.2013 23:07
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.
04.05.2013 02:00
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.
05.05.2013 07:39
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
28.12.2015 20:12
04.12.2017 14:05
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.
14.12.2017 02:57
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.
06.04.2018 17:25
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$.
19.01.2019 15:40
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$ .
12.04.2019 05:04
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.
18.07.2019 16:06
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\}$
21.05.2020 14:59
This problem is well known see here http://en.wikipedia.org/wiki/Artin's_conjecture_on_primitive_roots#Proof_attempts
06.06.2020 10:05
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)$.
18.06.2020 02:44
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.\]
18.06.2020 21:39
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$.
15.12.2020 00:18
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.
01.05.2021 14:41
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)$.
02.01.2022 00:04
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$).
02.01.2022 00:07
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
02.01.2022 00:14
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).
02.01.2022 00:16
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
02.01.2022 00:21
Yeah same I am bad under pressure.
29.10.2022 21:51
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?
16.08.2023 02:55
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$
23.02.2024 09:30
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: