Maths Olympiad Prep

Library / /110 of 169

Number theory Difficulty 7.5 National Olympiad, round 2 Prove it United States

Given positive integers mm and nn, prove that there is a positive integer cc such that the numbers cmcm and cncn have the same number of occurrences of each non-zero digit when written in base ten.

Solutions — 3

Solution 1

Solution 1 (By Richard Stong). For a given positive integer kk, write 10kmn=2r5st10^k m - n = 2^r 5^s t, where gcd(t,10)=1\text{gcd}(t, 10) = 1. For large enough values of kk, the number of times 2 and 5 divide the left-hand side is at most the number of times they divide nn, hence by choosing kk large we can make tt arbitrarily large. Choose kk so that tt is larger than either mm or nn.
Since tt is relatively prime to 10 there is a smallest exponent bb for which t(10b1)t \mid (10^b - 1). Thus bb is the number of digits in the repeating portion of the decimal expansion for 1t\frac{1}{t}. More precisely, if we write tc=(10b1)tc = (10^b - 1), then the repeating block is the bb-digit decimal representation of cc, obtained by prepending extra initial zeros to cc as necessary. Since tt is larger than mm or nn, the decimal expansions of mt\frac{m}{t} and nt\frac{n}{t} will consist of repeated bb-digit representations of cmcm and cncn, respectively. Rewriting the identity in the first line as
10k(mt)=2r5s+nt, 10^k \left( \frac{m}{t} \right) = 2^r 5^s + \frac{n}{t},
we see that the decimal expansion of nt\frac{n}{t} is obtained from that of mt\frac{m}{t} by shifting the decimal to the right kk places and removing the integer part. Thus the bb-digit representations of cmcm and cncn are cyclic shifts of one another. In particular, they have the same number of occurrences of each nonzero digit.

Solution 2 (By Zhou Xiaodong). Suppose without loss of generality that mnm \ge n. Note that if the desired holds for the pair (km,kn)(km, kn) for some kk, then it also holds for (m,n)(m, n). Write n=2a5bln = 2^a 5^b l for some ll relatively prime to 10, and note that it suffices to show the desired statement for the pair (2b5am,2b5an)=(2b5am,10a+bl)(2^b 5^a m, 2^b 5^a n) = (2^b 5^a m, 10^{a+b} l). Further, because 10a+bl10^{a+b} l ends with a string of a+ba+b trailing 0's it suffices to show the desired for the pair (2b5am,l)(2^b 5^a m, l), where gcd(l,10)=1\text{gcd}(l, 10) = 1. Thus, it suffices to consider (m,n)(m, n) with gcd(n,10)=1\text{gcd}(n, 10) = 1.
For such a pair (m,n)(m, n), we see that gcd(10mn,10)=1\text{gcd}(10m - n, 10) = 1, so we may find some kk and some cc so that
c(10mn)=10k1c(10m - n) = 10^k - 1, which after rearranging implies that
10cm+1=10k+cn. 10cm + 1 = 10^k + cn.
In addition, we see that 10k=10cmcn+1>10cncn=9cn>cn10^k = 10cm - cn + 1 > 10cn - cn = 9cn > cn, hence cm has exactly k digits and cn has l digits for l \le k. If cm=a1akcm = \overline{a_1 \cdots a_k} and cn=b2bk+1cn = \overline{b_2 \cdots b_{k+1}} are the decimal expansions of cm and cn (where some of the leading digits of cn may be 0), then the above equality yields the equality of decimal expansions
a1ak1=1b2bk+1. \overline{a_1 \cdots a_k 1} = \overline{1 b_2 \cdots b_{k+1}}.
We conclude that a1=bk+1=1a_1 = b_{k+1} = 1 and ai=bia_i = b_i for 2ik2 \le i \le k, so each non-zero digit appears among {ai}\{a_i\} and {bi}\{b_i\} the same number of times, hence appears in cn and cm the same number of times.

Solution 2

Since tt is relatively prime to 1010 there is a smallest exponent bb for which t(10b1)t \mid (10^b - 1). Thus bb is the number of digits in the repeating portion of the decimal expansion for 1t\frac{1}{t}. More precisely, if we write tc=(10b1)tc = (10^b - 1), then the repeating block is the bb-digit decimal representation of cc, obtained by prepending extra initial zeros to cc as necessary. Since tt is larger than mm or nn, the decimal expansions of mt\frac{m}{t} and nt\frac{n}{t} will consist of repeated bb-digit representations of cmcm and cncn, respectively. Rewriting the identity in the first line as
10k(mt)=2r5s+nt, 10^k \left(\frac{m}{t}\right) = 2^r 5^s + \frac{n}{t},
we see that the decimal expansion of nt\frac{n}{t} is obtained from that of mt\frac{m}{t} by shifting the decimal to the right kk places and removing the integer part. Thus the bb-digit representations of cmcm and cncn are cyclic shifts of one another. In particular, they have the same number of occurrences of each nonzero digit.

Solution 3

Suppose without loss of generality that mnm \ge n. Note that if the desired holds for the pair (km,kn)(km, kn) for some kk, then it also holds for (m,n)(m, n). Write n=2a5bln = 2^a 5^b l for some ll relatively prime to 1010, and note that it suffices to show the desired statement for the pair (2b5am,2b5an)=(2b5am,10a+bl)(2^b 5^a m, 2^b 5^a n) = (2^b 5^a m, 10^{a+b} l). Further, because 10a+bl10^{a+b} l ends with a string of a+ba+b trailing 0's it suffices to show the desired for the pair (2b5am,l)(2^b 5^a m, l), where gcd(l,10)=1\text{gcd}(l, 10) = 1. Thus, it suffices to consider (m,n)(m, n) with gcd(n,10)=1\text{gcd}(n, 10) = 1.
For such a pair (m,n)(m, n), we see that gcd(10mn,10)=1\text{gcd}(10m - n, 10) = 1, so we may find some kk and some cc so that
c(10mn)=10k1c(10m - n) = 10^k - 1, which after rearranging implies that
10cm+1=10k+cn. 10cm + 1 = 10^k + cn.
In addition, we see that 10k=10cmcn+1>10cncn=9cn>cn10^k = 10cm - cn + 1 > 10cn - cn = 9cn > cn, hence cmcm has exactly kk digits and cncn has ll digits for lkl \le k. If cm=a1akcm = \overline{a_1 \cdots a_k} and cn=b2bk+1cn = \overline{b_2 \cdots b_{k+1}} are the decimal expansions of cmcm and cncn (where some of the leading digits of cncn may be 00), then the above equality yields the equality of decimal expansions
a1ak1=1b2bk+1. \overline{a_1 \cdots a_k} \overline{1} = \overline{1} \overline{b_2 \cdots b_{k+1}}.
We conclude that a1=bk+1=1a_1 = b_{k+1} = 1 and ai=bia_i = b_i for 2ik2 \le i \le k, so each non-zero digit appears among {ai}\{a_i\} and {bi}\{b_i\} the same number of times, hence appears in cncn and cmcm the same number of times.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.