Maths Olympiad Prep

Library / /11 of 17

Number theory Difficulty 5.7 AIME, harder Prove it Mongolia

Let n3n \ge 3 be a given integer. Find the least number of digits in the number formed with only digits 11 and 22 such that the number is divisible by 10n710^n - 7.

Solution

Answer: 2n+12n + 1
Let N=ama2a1N = \overline{a_m \dots a_2 a_1} be a multiple of dd such that ai{1,2}a_i \in \{1, 2\} for every 1im1 \le i \le m, where dd denotes 10n710^n - 7. Since N2dN \ge 2d it is clear that mn+1m \ge n + 1. Suppose that 2nm2n \ge m. By setting S=7×aman+1+ana1S = 7 \times \overline{a_m \dots a_{n+1}} + \overline{a_n \dots a_1} we get
S7×222n+222n<2d. S \le 7 \times \underbrace{22\dots2}_{n} + \underbrace{22\dots2}_{n} < 2d.
It follows from dNd \mid N that dSd \mid S and so we must have S=dS = d ())\left(*)\right). But this equality is impossible. Indeed, by ())\left(*)\right), we have S7an+1+a1(mod10)S \equiv 7a_{n+1} + a_1 \pmod{10} which implies S≢3(mod10)S \not\equiv 3 \pmod{10} since a1,an+1{1,2}a_1, a_{n+1} \in \{1, 2\}. This contradicts to ())\left(*)\right). Thus m2n+1m \ge 2n + 1 and so, for our purpose, it suffices to show that 2111n1222n21112\underbrace{1\dots11}_{n-1}\underbrace{2\dots22}_{n-2}111 is divisible by dd:

2111n1222n2111=2×102n+111n12×10n+22n31112×72+7×111n12+22n311177n284+22n209=d0(modd). \begin{aligned} 2\underbrace{1\dots11}_{n-1}\underbrace{2\dots22}_{n-2}111 &= 2 \times 10^{2n} + \underbrace{1\dots11}_{n-1}2 \times 10^n + \underbrace{2\dots2}_{n-3}111 \\ &\equiv 2 \times 7^2 + 7 \times \underbrace{1\dots11}_{n-1}2 + \underbrace{2\dots2}_{n-3}111 \\ &\equiv \underbrace{7\dots7}_{n-2}84 + \underbrace{2\dots2}_{n-2}09 = d \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.