Find all positive integers n such that n 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 k is a positive integer, then there exist 0≤a1,a2,…,a2k≤9 such that a1,a3,…,a2k−1 are odd integers, a2,a4,…,a2k are even integers, and 22k+1∣a1a2⋯a2k Proof of Lemma 1 by mathematical induction. If k=1, it follows from 8∣16 that the proposition is true. Assume that if k=n−1, the proposition is true. When k=n, let a1a2⋯a2n−2=22n−1t by the inductive hypothesis. The problem reduces to proving that there exist 1≤a,b≤9 with a odd and b even such that 22n+1∣ab×102n−2+22n−1t, or 8∣ab×52n−2+2t, or 8∣ab+2t in view of 52n−2≡1(mod8). It follows from 8∣12+4, 8∣14+2, 8∣16+0 and 8∣50+6 that Lemma 1 is true.
Lemma 2: If k is a positive integer, then there exists an alternating number a1a2⋯a2k with an even number 2k of digits such that a2k is odd and 52k∣a1a2⋯a2k, where a1 can be 0, but a2=0. Proof of Lemma 2 by mathematical induction. If k=1, it follows from 25∣25 that the proposition is true. Assume that if k=n−1, the proposition is true, or there exists an alternating multiple a1a2⋯a2n−2 satisfying 52n−2∣a1a2⋯a2n−2. When k=n, let a1a2⋯a2n−2=t⋅52n−2. The problem reduces to proving that there exist 0≤a,b≤9 with a even and b odd such that 52∣ab×102n−2+t⋅52n−2, or 25∣ab×22n−2+t. Since 22n−2 is coprime to 25, there exist 0<ab≤25 such that 25∣ab×22n−2+t. If b is odd, between ab and ab+50, at least one satisfies that the highest-valued digit is even. If b is even, between ab+25 and ab+75, at least one satisfies that the highest-valued digit is even. This completes the proof of Lemma 2.
Let n=2α5βt, where t is coprime to 10 and α,β∈N. Assume that α≥2 and β≥1. Let l be an arbitrary multiple of n. The last decimal digit is 0, and the digit in tens is even. Hence these n do not satisfy the required condition.
① When α=β=0, consider 21, 2121, 212121, …, 2121…21, …. There must exist two of them congruent modulo n. Without loss of generality, we may assume that t1>t2, and number t1 of 212121⋯21≡number t2 of 212121⋯21(modn). Then number t1−t2 of 212121⋯21≡number 2t2 of 000⋯0≡0(modn) Hence number t1−t2 of 212121⋯21≡0(modn), because n is coprime to 10. Now these positive integers n satisfy the required condition.
② When β=0 and α≥1, it follows from Lemma 1 that there exists an alternating number a1a2⋯a2k satisfying 2α∣a1a2⋯a2k. Consider a1a2⋯a2k,a1a2⋯a2ka1a2⋯a2k,…,a1a2⋯a2ka1a2⋯a2k⋯a1a2⋯a2k,… There must exist two of them congruent modulo t. Without loss of generality, we may assume that t1>t2, and a1a2⋯a2k⋯a1a2⋯a2k≡a1a2⋯a2k⋯a1a2⋯a2k(modt) Since t is coprime to 10, a1a2⋯a2k⋯a1a2⋯a2k≡0(modt). Moreover, since t is coprime to 2, 2αt∣a1a2⋯a2k⋯a1a2⋯a2k, which is alternating.
③ When α=0,β≥1, it follows from Lemma 2 that there exists an alternating multiple a1a2⋯a2k satisfying 5β∣a1a2⋯a2k with a2k odd. Using the same argument as in ②, we obtain that there exist t1>t2 satisfying t∣a1a2⋯a2k⋯a1a2⋯a2k. Since t is coprime to 5, 5βt∣a1a2⋯a2k⋯a1a2⋯a2k In addition, a1a2⋯a2k⋯a1a2⋯a2k is alternating, and the last decimal digit a2k is odd.
④ When α=1 and β≥1, it follows from ③ that there exists an alternating number a1a2⋯a2k⋯a1a2⋯a2k satisfying that a2k is odd and 5βt∣a1a2⋯a2k⋯a1a2⋯a2k. Hence 2⋅5βt∣a1a2⋯a2k⋯a1a2⋯a2k, which is alternating.
In conclusion, if n is not divisible by 20, then these positive integers n satisfy the required condition.
Solution II
n should be the positive integers and should satisfy that n is not divisible by 20.
(1) Assume that 20∣n. Select a multiple of n arbitrarily. Denote (akak−1⋯a1)10, where ak=0. We have 20∣(akak−1⋯a1)10. Hence a1=0, 2∣(akak−1⋯a1)10. This implies that a2 is even. Therefore, (akak−1⋯a1)10 is not alternating.
(2) We will prove that if n is a positive integer and is not divisible by 20, then n 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 n is coprime to 10, then for any l∈N, there exists k∈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 n. Proof of Lemma 1: Consider the numbers x1=1,x2=1number l of 000⋯0,…, xm=1number l of 000⋯01⋯1number l of 000⋯01,… There must exist two of them congruent modulo n. Without loss of generality, we may assume that xs≡xt(mod n),s>t≥1. Then n∣xs−xt. Moreover, since xs−xt=xs−t⋅10t(l+1) and n is coprime to 10, n∣xs−t, s−t>0 and xs−t is a positive integer. This completes the proof of Lemma 1.
Lemma 2: For any m∈N, there always exists an alternating number sm with m digits such that its first digit can be 0, and its last decimal digit is 5, and 5m∣sm. Proof of Lemma 2 by inductive construction. Start with s1=5. Suppose that sm=(amam−1⋯a1)10 is alternating, where a1=5 and am can be 0. In addition, 5m∣sm. Let sm=5m. Denote A={{0,2,4,6,8},{1,3,5,7,9},when am is odd,when am is even. Any two of them in A are not congruent modulo 5, and 2m is coprime to 5. So any two of the numbers in {2mx∣x∈A} are not congruent modulo 5. Select x∈A such that 2mx=−l(mod5). Then 5∣2mx+l. Let sm+1=(xamam−1⋯a1)10. Then sm+1 is an alternating number with m+1 digits, where a1=5, and its first digit can be 0. In addition, sm+1=x10m+sm=5m(2mx+l) is a multiple of 5m+1. This completes the proof of Lemma 2.
Lemma 3: For any integer m∈N, there always exists an alternating number tm with m digits such that its last decimal digit is 2, and 22k+1∣t2k+1,22k+3∣t2k+2. Proof of Lemma 3 by inductive construction. Start with t1=2. Suppose that t2k+1=(a2k+1a2k⋯a1)10 is alternating, where a1=2, and 22k+1∣t2k+1. It follows from the property of the alternating numbers that a2k+1=a1=0(mod2). Denote A={1,3,5,7}. Any two of them in A are not congruent modulo 8, and 52k+1 is coprime to 8. So any two numbers of {52k+1x∣x∈A} are not congruent modulo 8. Now divide the four numbers in {52k+1x∣x∈A} by 8 respectively. The original sentence means the 4 numbers are divisible by 8. Since 52k+1x with x∈A is odd, the remainders are 1, 3, 5, 7. Let t2k+1=22k+1l with l odd. Select x∈A such that 52k+1x≡−l+4(mod8). Then 22∤52k+1x+l. Let t2k+2=(xa2k+1⋯a1)10. Then t2k+2 is alternating with 2k+2 digits. In addition, a1=2 and t2k+2=x102k+1+t2k+1=22k+1(52k+1x+l). Since 22∤52k+1x+l, we have 22k+3∤t2k+2. Moreover, suppose that t2k+2=(a2k+2⋯a1)10, where a1=2, and 22k+3∤t2k+2. Let t2k+3=(4a2k+2⋯a1)10. Then t2k+3 is an alternating number with 2k+3 digits, and t2k+3=52k+222k+4+t2k+2. Since 22k+3∤t2k+2, we have 22k+3∤t2k+3. This completes the proof of Lemma 3.
Next, we discuss the four cases. (1) If n is coprime to 10, it follows from Lemma 1 that there exists k∈N∗ such that 10101⋯101 is a multiple of n. The conclusion is equivalent to selecting l=1 in Lemma 1. (2) If n is not divisible by 5, and n is divisible by 2, let n=2mn0 such that n0 is not divisible by 2, then n0 is coprime to 10. Select m0>m with m0 even. It follows from Lemma 3 that there exists an alternating number tm0=(am0⋯a1)10 with m0 digits, where a1=2. In addition, 2m0+1∤tm0. Hence 2m∣tm0. It follows from Lemma 1 that there exists k∈N∗ such that P=tm0⋅1number m,−1 of 0number k of 100⋯0⋅1⋯100⋯01 can be divisible by 2mn0, or n∣P. (3) If n is divisible by 5, and n is not divisible by 2, let n=5mn0 such that n0 is not divisible by 5, then n0 is coprime to 10. Select m0>m with m0 even. It follows from Lemma 2 that there exist an alternating number sm0=(am0⋯a1)10 with m0 digits, where a1=5 and am0 can be 0. In addition, 5m∣sm0. Hence 5m∣sm0. Using the same argument as (2), there exists an alternating number P such that 5mn0∣P and the last decimal digit a1=5. (4) If n is divisible by 10, and n is not divisible by 20, let n=10n0 with n0 odd, then n0 satisfies the assumption in case (1) or in case (3). It follows from (1) and (3) that there exists (ak⋯a1)10 an alternating multiple of n0, where a1=1 or 5. Now let P=(ak⋯a10)10. Then P is an alternating multiple of n.
In conclusion, n 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.