Maths Olympiad Prep

Library / /22 of 32

Number theory Difficulty 6.1 National Olympiad Prove it Romania

Find all positive integers NN having an even number of digits (no leading zeroes) such that, if we insert a multiplication sign after the first nn digits of NN, the result of the multiplication is a divisor of NN.

Solutions — 2

Solution 1

Let N=a1a2anb1b2bnN = \overline{a_1a_2\dots a_n b_1b_2\dots b_n} be the 2n2n-digit number, with a11a_1 \ge 1. Also let A=a1a2anA = \overline{a_1a_2\dots a_n} and B=b1b2bnB = \overline{b_1b_2\dots b_n}, so by hypothesis we are given 10nA+B=N=kAB10^n A + B = N = kAB for some positive integer kk. Multiplying with kk and adding 10n10^n, we arrive at (kA1)(kB10n)=10n(kA - 1)(kB - 10^n) = 10^n.

For n=1n = 1 we immediately solve (kA1)(kB10)=10(kA-1)(kB-10) = 10, with AA and BB not-null digits, to obtain N{11,12,15,24,36}N \in \{11, 12, 15, 24, 36\}.

For n2n \ge 2 we have 10n1A<10n10^{n-1} \le A < 10^n and 1B<10n1 \le B < 10^n, thus 1<k<101 < k < 10. A case-by-case discussion follows.

* k=2k=2. Then 210n112A110n2 \cdot 10^{n-1} - 1 \le 2A - 1 \mid 10^n, so 2A15n2A - 1 \le 5^n, forcing n2n \le 2. From (2A1)(2B100)=100(2A-1)(2B-100) = 100 we get N=1352N = 1352.

* k=3k=3. Then 310n113A110n3 \cdot 10^{n-1} - 1 \le 3A - 1 \mid 10^n. We cannot have 3A1=10n3A - 1 = 10^n, impossible modulo 3. We cannot have 3A1=210n13A - 1 = 2 \cdot 10^{n-1}, because it is too small. For 3A1=510n13A - 1 = 5 \cdot 10^{n-1}, we get A=510n1+13A = \frac{5 \cdot 10^{n-1} + 1}{3} and B=2A=10n+23B = 2A = \frac{10^n + 2}{3} (for example, for n=2n=2 we get N=1734N = 1734). Thus we get a first infinite family of solutions.

* k=4k=4. Then 410n114A110n4 \cdot 10^{n-1} - 1 \le 4A - 1 \mid 10^n, so 4A15n4A - 1 \le 5^n, impossible.

* k=5k=5. Then 510n115A110n5 \cdot 10^{n-1} - 1 \le 5A - 1 \mid 10^n, so 5A12n5A - 1 \le 2^n, impossible.

* k=6k=6. Then 610n116A110n6 \cdot 10^{n-1} - 1 \le 6A - 1 \mid 10^n, so 6A110n6A - 1 \le 10^n, which forces 6A1=10n6A - 1 = 10^n, impossible modulo 3.

* k=7k=7. Then 710n117A110n7 \cdot 10^{n-1} - 1 \le 7A - 1 \mid 10^n, so 7A110n7A - 1 \le 10^n, which forces (as in the above) 7A1=10n7A - 1 = 10^n. This leads to A=B=10n+17A = B = \frac{10^n + 1}{7}, with only proviso that nn is an odd multiple of 3 in order to A,BA, B to be integer (for example, for n=3n=3 we get N=143143N = 143143, while for n=9n=9 we get N=142857143142857143N = 142857143142857143). Thus we arrive at a second infinite family of solutions.

* k=8k=8 and k=9k=9 don't work, since they force kA1=10nkA - 1 = 10^n, impossible modulo 2 or modulo 3.

Thus, wrapping things up, the solutions are N{11,12,15,24,36}N \in \{11, 12, 15, 24, 36\}, the isolated value N=1352N = 1352, and the two infinite families described in the above.

Solution 2

With the above notations, from kAB=10nA+BkAB = 10^n A + B, we get that 10nA=B(kA1)10^n A = B(kA-1), so AB(kA1)A \mid B(kA-1). Since (A,kA1)=1(A, kA-1) = 1, we have ABA \mid B, so B=pAB = pA, where pNp \in \mathbb{N}^*. It follows that p(kA1)=10np(kA-1) = 10^n, so p10np \mid 10^n. As AA and BB are nn-digit numbers, we have 1p<101 \le p < 10, so p{1,2,4,5,8}p \in \{1, 2, 4, 5, 8\}.

Moreover, from p(kA1)=10np(kA-1) = 10^n and 10n1AB<10n10^{n-1} \le A \le B < 10^n, we get that 1+p10n<k10p+110n11 + \frac{p}{10^n} < k \le \frac{10}{p} + \frac{1}{10^{n-1}}, so 2k10p+110n12 \le k \le \frac{10}{p} + \frac{1}{10^{n-1}}. In order to improve this bounding, we'll study separately n=1n=1, in which case we easily find the solutions N{11,12,15,24,36}N \in \{11, 12, 15, 24, 36\}.

For n2n \ge 2, it follows that we have 2k10p2 \le k \le \frac{10}{p}, which immediately drops the case p=8p=8. Also, for p{4,5}p \in \{4, 5\}, we must have k=2k=2. If p=5p=5, then 2A1=510n12A - 1 = 5 \cdot 10^{n-1}, impossible, for parity reasons. If p=4p = 4, we get 2A1=2510n22A - 1 = 25 \cdot 10^{n-2}. Again, parity arguments provide n=2n = 2, so A=13A = 13 and B=52B = 52, so N=1352N = 1352. That leaves us with p{1,2,4}p \in \{1, 2, 4\}.

For p=1p = 1, we have 2k102 \le k \le 10 and kA=10n+1kA = 10^n + 1, so kk must be odd, and it cannot be 5 or divisible by 3. The only possibility remains k=7k = 7, which works only if 710n+17 \mid 10^n + 1; we get that n=6t+3n = 6t + 3, tNt \in \mathbb{N}, so
A=B=106t+3+17andN=142857142857t times 142857143. A = B = \frac{10^{6t+3} + 1}{7} \quad \text{and} \quad N = \underbrace{142\,857 \dots 142\,857}_{t \text{ times } 142857} 143.

For p=2p = 2, we have 2k52 \le k \le 5 and kA=510n1+1kA = 5 \cdot 10^{n-1} + 1, so kk is odd and it is not 5, so it must be 3 (which works for all n1n \ge 1). It follows that
A=510n1+13,B=10n+23,N=166673334n1 times 6,n times 3 A = \frac{5 \cdot 10^{n-1} + 1}{3}, \quad B = \frac{10^n + 2}{3}, \quad N = \underbrace{1\,66\dots6\,7\,33\dots3\,4}_{n-1 \text{ times } 6}, \quad \underbrace{\text{n times 3}}

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.