Maths Olympiad Prep

Library / /13 of 17

Number theory Difficulty 6.6 National olympiad Prove it Mongolia

Find the least number of digits in the multiple of 102025+310^{2025} + 3 such that the number of different digits in it is exactly two.

Solution

Answer: 4050
Put n=2025n = 2025 and d=10n+3d = 10^n + 3. Let N=ama2a1N = \overline{a_m \dots a_2 a_1} be a multiple of dd such that the number of different digits in NN is at most two. Then we can assume that a10a_1 \ne 0 and clearly mn+1m \ge n+1 since NdN \ge d. Suppose that 2n>m2n > m, and consider A=ana1A = \overline{a_n \dots a_1} and B=aman+1B = \overline{a_m \dots a_{n+1}}. Since d>3×10n1>3Bd > 3 \times 10^{n-1} > 3B and d>Ad > A we have A3B<d|A - 3B| < d. Moreover, A3B=NdBA - 3B = N - dB is a multiple of dd and so A=3BA = 3B, or equivalently,
ana1=3×aman+1.(0.2) \overline{a_n \dots a_1} = 3 \times \overline{a_m \dots a_{n+1}}. \qquad (0.2)
If an=0a_n = 0 then an+1=a1a_{n+1} = a_1 since an+10a_{n+1} \ne 0 and a10a_1 \ne 0. Therefore, a1=5a_1 = 5 and 3an+2+1a2(mod10)3a_{n+2} + 1 \equiv a_2 \pmod{10} by (0.2). But this is impossible since a2,an+2{0,5}a_2, a_{n+2} \in \{0, 5\}. Thus an0a_n \ne 0 and so it follows from (0.2) that m=2n1m = 2n - 1. Moreover, we have anan1=3am+c\overline{a_n a_{n-1}} = 3a_m + c for some digit cc. Observe that 1an21 \le a_n \le 2 and 0c20 \le c \le 2 since 3B<3×10n13B < 3 \times 10^{n-1} and 3×am1an+1<3×10n23 \times \overline{a_{m-1} \dots a_{n+1}} < 3 \times 10^{n-2}.
Assume that an=2a_n = 2. If a1=2a_1 = 2 then an+1=4a_{n+1} = 4 by (0.2). Hence c=anan13am223×4=10c = \overline{a_n a_{n-1}} - 3a_m \ge 22 - 3 \times 4 = 10, a contradiction. If an+1=2a_{n+1} = 2 then a1=6a_1 = 6 and so c223×6=4c \ge 22 - 3 \times 6 = 4, a contradiction.
Assume that an=1a_n = 1. If an+1=1a_{n+1} = 1 then a1=3a_1 = 3, hence (0.2) is impossible. If a1=1a_1 = 1 then an+1=7a_{n+1} = 7, hence c113×1=8c \ge 11 - 3 \times 1 = 8, a contradiction.
Thus m2nm \ge 2n and so it suffices to show that 2n2n-digit number 111 333\overline{1 \dots 11 \ 3 \dots 33} is divisible by dd:
111 333=111×10n+333=111×(d3)+3×1110(modd). \begin{aligned} \overline{1 \dots 11 \ 3 \dots 33} &= \overline{1 \dots 11} \times 10^n + \overline{3 \dots 33} \\ &= \overline{1 \dots 11} \times (d-3) + 3 \times \overline{1 \dots 11} \equiv 0 \pmod{d}. \end{aligned}

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.