Maths Olympiad Prep

Library / /75 of 106

Number theory Difficulty 8.6 Shortlist Prove it China

Find all positive integers nn such that nn has a multiple which is alternating.

We call a positive integer alternating if every two consecutive digits in its decimal representation are of different parity.

Solution

Solution I

Lemma 1: If kk is a positive integer, then there exist 0a1,a2,,a2k90 \le a_1, a_2, \dots, a_{2k} \le 9 such that a1,a3,,a2k1a_1, a_3, \dots, a_{2k-1} are odd integers, a2,a4,,a2ka_2, a_4, \dots, a_{2k} are even integers, and
22k+1a1a2a2k 2^{2k+1} \mid \overline{a_1 a_2 \cdots a_{2k}}
Proof of Lemma 1 by mathematical induction.
If k=1k=1, it follows from 8168 \mid 16 that the proposition is true.
Assume that if k=n1k = n-1, the proposition is true.
When k=nk=n, let a1a2a2n2=22n1t\overline{a_1 a_2 \cdots a_{2n-2}} = 2^{2n-1}t by the inductive hypothesis.
The problem reduces to proving that there exist 1a,b91 \le a, b \le 9 with aa odd and bb even such that 22n+1ab×102n2+22n1t2^{2n+1} \mid \overline{ab} \times 10^{2n-2} + 2^{2n-1}t, or 8ab×52n2+2t8 \mid \overline{ab} \times 5^{2n-2} + 2t, or 8ab+2t8 \mid \overline{ab} + 2t in view of 52n21(mod8)5^{2n-2} \equiv 1 \pmod 8.
It follows from 812+48|12+4, 814+28|14+2, 816+08|16+0 and 850+68|50+6 that Lemma 1 is true.

Lemma 2: If kk is a positive integer, then there exists an alternating number a1a2a2k\overline{a_1 a_2 \cdots a_{2k}} with an even number 2k2k of digits such that a2ka_{2k} is odd and 52ka1a2a2k5^{2k} \mid \overline{a_1 a_2 \cdots a_{2k}}, where a1a_1 can be 0, but a20a_2 \ne 0.
Proof of Lemma 2 by mathematical induction.
If k=1k=1, it follows from 252525 \mid 25 that the proposition is true.
Assume that if k=n1k=n-1, the proposition is true, or there exists an alternating multiple a1a2a2n2\overline{a_1 a_2 \cdots a_{2n-2}} satisfying 52n2a1a2a2n25^{2n-2} \mid \overline{a_1 a_2 \cdots a_{2n-2}}.
When k=nk=n, let a1a2a2n2=t52n2\overline{a_1 a_2 \cdots a_{2n-2}} = t \cdot 5^{2n-2}. The problem reduces to proving that there exist 0a,b90 \le a, b \le 9 with aa even and bb odd such that 52ab×102n2+t52n25^2 \mid \overline{ab} \times 10^{2n-2} + t \cdot 5^{2n-2}, or 25ab×22n2+t25 \mid \overline{ab} \times 2^{2n-2} + t.
Since 22n22^{2n-2} is coprime to 25, there exist 0<ab250 < \overline{ab} \le 25 such that 25ab×22n2+t25 \mid \overline{ab} \times 2^{2n-2} + t. If bb is odd, between ab\overline{ab} and ab+50\overline{ab} + 50, at least one satisfies that the highest-valued digit is even. If bb is even, between ab+25\overline{ab} + 25 and ab+75\overline{ab} + 75, at least one satisfies that the highest-valued digit is even.
This completes the proof of Lemma 2.

Let n=2α5βtn = 2^\alpha 5^\beta t, where tt is coprime to 10 and α,βN\alpha, \beta \in \mathbb{N}. Assume that α2\alpha \ge 2 and β1\beta \ge 1. Let ll be an arbitrary multiple of nn. The last decimal digit is 0, and the digit in tens is even. Hence these nn do not satisfy the required condition.

① When α=β=0\alpha = \beta = 0, consider 2121, 21212121, 212121212121, \dots, 2121212121\dots21, \dots. There must exist two of them congruent modulo nn.
Without loss of generality, we may assume that t1>t2t_1 > t_2, and
212121number t1 of 21212121number t2 of 21(modn). \underbrace{2121\cdots21}_{\text{number } t_1 \text{ of } 21} \equiv \underbrace{2121\cdots21}_{\text{number } t_2 \text{ of } 21} \pmod{n}.
Then
212121number t1t2 of 21000number 2t2 of 00(modn) \underbrace{2121\cdots21}_{\text{number } t_1-t_2 \text{ of } 21} \equiv \underbrace{00\cdots0}_{\text{number } 2t_2 \text{ of } 0} \equiv 0 \pmod{n}
Hence
212121number t1t2 of 210(modn), \underbrace{2121\cdots21}_{\text{number } t_1-t_2 \text{ of } 21} \equiv 0 \pmod{n},
because nn is coprime to 10.
Now these positive integers nn satisfy the required condition.

② When β=0\beta = 0 and α1\alpha \ge 1, it follows from Lemma 1 that there exists an alternating number a1a2a2k\overline{a_1 a_2 \cdots a_{2k}} satisfying 2αa1a2a2k2^\alpha \mid \overline{a_1 a_2 \cdots a_{2k}}. Consider
a1a2a2k,a1a2a2ka1a2a2k,,a1a2a2ka1a2a2ka1a2a2k, \overline{a_1 a_2 \cdots a_{2k}}, \overline{a_1 a_2 \cdots a_{2k} a_1 a_2 \cdots a_{2k}}, \dots, \overline{a_1 a_2 \cdots a_{2k} a_1 a_2 \cdots a_{2k} \cdots a_1 a_2 \cdots a_{2k}}, \dots
There must exist two of them congruent modulo tt. Without loss of generality, we may assume that t1>t2t_1 > t_2, and
a1a2a2ka1a2a2ka1a2a2ka1a2a2k(modt) \overline{a_1 a_2 \cdots a_{2k} \cdots a_1 a_2 \cdots a_{2k}} \equiv \overline{a_1 a_2 \cdots a_{2k} \cdots a_1 a_2 \cdots a_{2k}} \pmod{t}
Since tt is coprime to 10, a1a2a2ka1a2a2k0(modt)\overline{a_1 a_2 \cdots a_{2k} \cdots a_1 a_2 \cdots a_{2k}} \equiv 0 \pmod{t}. Moreover, since tt is coprime to 2,
2αta1a2a2ka1a2a2k, 2^\alpha t \mid \overline{a_1 a_2 \cdots a_{2k} \cdots a_1 a_2 \cdots a_{2k}},
which is alternating.

③ When α=0,β1\alpha = 0, \beta \ge 1, it follows from Lemma 2 that there exists an alternating multiple a1a2a2k\overline{a_1 a_2 \cdots a_{2k}} satisfying 5βa1a2a2k5^\beta \mid \overline{a_1 a_2 \cdots a_{2k}} with a2ka_{2k} odd. Using the same argument as in ②, we obtain that there exist t1>t2t_1 > t_2 satisfying ta1a2a2ka1a2a2kt \mid \overline{a_1 a_2 \cdots a_{2k} \cdots a_1 a_2 \cdots a_{2k}}. Since tt is coprime to 5,
5βta1a2a2ka1a2a2k 5^{\beta_t} \mid \overline{a_1 a_2 \cdots a_{2k} \cdots a_1 a_2 \cdots a_{2k}}
In addition, a1a2a2ka1a2a2k\overline{a_1 a_2 \cdots a_{2k} \cdots a_1 a_2 \cdots a_{2k}} is alternating, and the last decimal digit a2ka_{2k} is odd.

④ When α=1\alpha = 1 and β1\beta \ge 1, it follows from ③ that there exists an alternating number a1a2a2ka1a2a2k\overline{a_1 a_2 \cdots a_{2k} \cdots a_1 a_2 \cdots a_{2k}} satisfying that a2ka_{2k} is odd and 5βta1a2a2ka1a2a2k5^{\beta_t} \mid \overline{a_1 a_2 \cdots a_{2k} \cdots a_1 a_2 \cdots a_{2k}}. Hence 25βta1a2a2ka1a2a2k2 \cdot 5^{\beta_t} \mid \overline{a_1 a_2 \cdots a_{2k} \cdots a_1 a_2 \cdots a_{2k}}, which is alternating.

In conclusion, if nn is not divisible by 20, then these positive integers nn satisfy the required condition.

Solution II

nn should be the positive integers and should satisfy that nn is not divisible by 20.

(1) Assume that 20n20 \mid n. Select a multiple of nn arbitrarily. Denote (akak1a1)10(a_k a_{k-1} \cdots a_1)_{10}, where ak0a_k \ne 0. We have 20(akak1a1)1020 \mid (a_k a_{k-1} \cdots a_1)_{10}. Hence a1=0a_1 = 0, 2(akak1a1)102 \mid (a_k a_{k-1} \cdots a_1)_{10}. This implies that a2a_2 is even. Therefore, (akak1a1)10(a_k a_{k-1} \cdots a_1)_{10} is not alternating.

(2) We will prove that if nn is a positive integer and is not divisible by 20, then nn must have a multiple which is alternating.
We will show three lemmas as follows. Then we divide the proof into four cases.

Lemma 1: If the positive integer nn is coprime to 10, then for any lNl \in \mathbb{N}, there exists kNk \in \mathbb{N} such that
\frac{\begin{array}{c} 1 \ 00\cdots0 \\ \underline{\quad} \\ \mathbf{number} \ l \ \mathbf{of} \ 0 \end{array} \quad \begin{array}{c} 1 \ 00\cdots0 \\ \underline{\quad} \\ \mathbf{number} \ l \ \mathbf{of} \ 0 \end{array} \quad \begin{array}{c} 1 \cdots 1 \ 00\cdots0 \\ \underline{\quad} \\ \mathbf{number} \ l \ \mathbf{of} \ 0 \end{array} \quad \begin{array}{c} 1 \\ \underline{\quad} \\ \mathbf{total number} \ k \ \mathbf{of} \ 1 \end{array}}
is a multiple of nn.
Proof of Lemma 1: Consider the numbers x1=1,x2=1000number l of 0,,x_1 = 1, x_2 = 1 \underbrace{00\cdots0}_{\text{number } l \text{ of } 0}, \dots,
xm=1000number l of 0 11000number l of 0 1, x_m = 1 \underbrace{00\cdots0}_{\text{number } l \text{ of } 0} \ 1 \cdots 1 \underbrace{00\cdots0}_{\text{number } l \text{ of } 0} \ 1, \dots
There must exist two of them congruent modulo nn. Without loss of generality, we may assume that
xsxt(mod n),s>t1. x_s \equiv x_t (\text{mod } n), s > t \ge 1.
Then nxsxtn \mid x_s - x_t. Moreover, since xsxt=xst10t(l+1)x_s - x_t = x_{s-t} \cdot 10^{t(l+1)} and nn is coprime to 1010, nxstn \mid x_{s-t}, st>0s-t > 0 and xstx_{s-t} is a positive integer. This completes the proof of Lemma 1.

Lemma 2: For any mNm \in \mathbb{N}, there always exists an alternating number sms_m with mm digits such that its first digit can be 0, and its last decimal digit is 5, and 5msm5^m \mid s_m.
Proof of Lemma 2 by inductive construction. Start with s1=5s_1 = 5. Suppose that sm=(amam1a1)10s_m = (a_m a_{m-1} \cdots a_1)_{10} is alternating, where a1=5a_1 = 5 and ama_m can be 0. In addition, 5msm5^m \mid s_m. Let sm=5ms_m = 5^m. Denote
A={{0,2,4,6,8},when am is odd,{1,3,5,7,9},when am is even. A = \begin{cases} \{0, 2, 4, 6, 8\}, & \text{when } a_m \text{ is odd,} \\ \{1, 3, 5, 7, 9\}, & \text{when } a_m \text{ is even.} \end{cases}
Any two of them in AA are not congruent modulo 55, and 2m2^m is coprime to 55. So any two of the numbers in {2mxxA}\{2^m x \mid x \in A\} are not congruent modulo 55. Select xAx \in A such that 2mx=l(mod5)2^m x = -l \pmod 5. Then 52mx+l5 \mid 2^m x + l. Let sm+1=(xamam1a1)10s_{m+1} = (x a_m a_{m-1} \cdots a_1)_{10}. Then sm+1s_{m+1} is an alternating number with m+1m+1 digits, where a1=5a_1 = 5, and its first digit can be 0. In addition, sm+1=x10m+sm=5m(2mx+l)s_{m+1} = x 10^m + s_m = 5^m(2^m x + l) is a multiple of 5m+15^{m+1}. This completes the proof of Lemma 2.

Lemma 3: For any integer mNm \in \mathbb{N}, there always exists an alternating number tmt_m with mm digits such that its last decimal digit is 2, and
22k+1t2k+1,22k+3t2k+2. 2^{2k+1} \mid t_{2k+1}, \quad 2^{2k+3} \mid t_{2k+2}.
Proof of Lemma 3 by inductive construction. Start with t1=2t_1 = 2. Suppose that t2k+1=(a2k+1a2ka1)10t_{2k+1} = (a_{2k+1} a_{2k} \cdots a_1)_{10} is alternating, where a1=2a_1 = 2, and 22k+1t2k+12^{2k+1} \mid t_{2k+1}. It follows from the property of the alternating numbers that a2k+1=a1=0(mod2)a_{2k+1} = a_1 = 0 \pmod 2.
Denote A={1,3,5,7}A = \{1, 3, 5, 7\}. Any two of them in AA are not congruent modulo 88, and 52k+15^{2k+1} is coprime to 88. So any two numbers of {52k+1xxA}\{5^{2k+1} x \mid x \in A\} are not congruent modulo 88. Now divide the four numbers in {52k+1xxA}\{5^{2k+1} x \mid x \in A\} by 88 respectively. The original sentence means the 4 numbers are divisible by 8. Since 52k+1x5^{2k+1}x with xAx \in A is odd, the remainders are 1, 3, 5, 7.
Let t2k+1=22k+1lt_{2k+1} = 2^{2k+1}l with ll odd. Select xAx \in A such that 52k+1xl+4(mod8)5^{2k+1}x \equiv -l+4 \pmod 8. Then 2252k+1x+l2^2 \nmid 5^{2k+1}x+l. Let t2k+2=(xa2k+1a1)10t_{2k+2} = (x a_{2k+1} \cdots a_1)_{10}. Then t2k+2t_{2k+2} is alternating with 2k+22k+2 digits. In addition, a1=2a_1 = 2 and t2k+2=x102k+1+t2k+1=22k+1(52k+1x+l)t_{2k+2} = x 10^{2k+1} + t_{2k+1} = 2^{2k+1}(5^{2k+1}x+l).
Since 2252k+1x+l2^2 \nmid 5^{2k+1}x+l, we have 22k+3t2k+22^{2k+3} \nmid t_{2k+2}.
Moreover, suppose that t2k+2=(a2k+2a1)10t_{2k+2} = (a_{2k+2} \cdots a_1)_{10}, where a1=2a_1 = 2, and 22k+3t2k+22^{2k+3} \nmid t_{2k+2}. Let t2k+3=(4a2k+2a1)10t_{2k+3} = (4 a_{2k+2} \cdots a_1)_{10}. Then t2k+3t_{2k+3} is an alternating number with 2k+32k+3 digits, and t2k+3=52k+222k+4+t2k+2t_{2k+3} = 5^{2k+2}2^{2k+4} + t_{2k+2}.
Since 22k+3t2k+22^{2k+3} \nmid t_{2k+2}, we have 22k+3t2k+32^{2k+3} \nmid t_{2k+3}. This completes the proof of Lemma 3.

Next, we discuss the four cases.
(1) If nn is coprime to 10, it follows from Lemma 1 that there exists kNk \in N^* such that 10 10110110 \ 101 \cdots 101 is a multiple of nn. The conclusion is equivalent to selecting l=1l=1 in Lemma 1.
(2) If nn is not divisible by 5, and nn is divisible by 2, let n=2mn0n = 2^m n_0 such that n0n_0 is not divisible by 2, then n0n_0 is coprime to 10. Select m0>mm_0 > m with m0m_0 even. It follows from Lemma 3 that there exists an alternating number tm0=(am0a1)10t_{m_0} = (a_{m_0} \cdots a_1)_{10} with m0m_0 digits, where a1=2a_1 = 2. In addition, 2m0+1tm02^{m_0+1} \nmid t_{m_0}. Hence 2mtm02^m \mid t_{m_0}. It follows from Lemma 1 that there exists kNk \in N^* such that
P=tm01000number m,1 of 0number k of 1110001 P = t_{m_0} \cdot 1 \underbrace{00\cdots0}_{\substack{\text{number } m, -1 \text{ of } 0 \\ \text{number } k \text{ of } 1}} \cdot 1\cdots100\cdots01
can be divisible by 2mn02^m n_0, or nPn \mid P.
(3) If nn is divisible by 5, and nn is not divisible by 2, let n=5mn0n = 5^m n_0 such that n0n_0 is not divisible by 5, then n0n_0 is coprime to 10. Select m0>mm_0 > m with m0m_0 even. It follows from Lemma 2 that there exist an alternating number sm0=(am0a1)10s_{m_0} = (a_{m_0} \cdots a_1)_{10} with m0m_0 digits, where a1=5a_1 = 5 and am0a_{m_0} can be 0. In addition, 5msm05^m \mid s_{m_0}. Hence 5msm05^m \mid s_{m_0}. Using the same argument as (2), there exists an alternating number PP such that 5mn0P5^m n_0 \mid P and the last decimal digit a1=5a_1 = 5.
(4) If nn is divisible by 10, and nn is not divisible by 20, let n=10n0n = 10n_0 with n0n_0 odd, then n0n_0 satisfies the assumption in case (1) or in case (3). It follows from (1) and (3) that there exists (aka1)10(a_k \cdots a_1)_{10} an alternating multiple of n0n_0, where a1=1a_1 = 1 or 5. Now let P=(aka10)10P = (a_k \cdots a_1 0)_{10}. Then PP is an alternating multiple of nn.

In conclusion, nn should be a positive integer and should not be divisible by 20.

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 and solution reproduced as published; topic and difficulty added by this site.