Maths Olympiad Prep

Library / /267 of 462

, 2014

Number theory Difficulty 6.0 AIME, harder Prove it Ireland

Suppose (an)(a_n) is a sequence of integers such that a1a_1 and a2a_2 are two distinct digits of the number 20142014, and an=an110+an210a_n = a_{n-1}^{10} + a_{n-2}^{10} for all n>2n > 2.
Let m=201420142014m = 20142014\ldots2014 be the number given by the string 20142014 repeated 20142014 times. Show that mm cannot be ana_n for any positive integer nn.

Solution

Note first that
a3=a110+a210210+410<2410=221<1021<manda4=a210+a310<410+1020<21020<m. \begin{align*} a_3 &= a_1^{10} + a_2^{10} \le 2^{10} + 4^{10} < 2 \cdot 4^{10} = 2^{21} < 10^{21} < m \quad \text{and} \\ a_4 &= a_2^{10} + a_3^{10} < 4^{10} + 10^{20} < 2 \cdot 10^{20} < m. \end{align*}
Hence, if m=anm = a_n, then n5n \ge 5.
Given the possible values for a1a_1 and a2a_2, we see that a3a_3 is congruent to either 11 or 22 modulo 33, depending on whether or not we select 00 as one of the two initial terms of the sequence. Similarly, a4a_4 is congruent to either 11 or 22 modulo 33, depending on whether or not a2=0a_2 = 0. In any case, neither a3a_3 nor a4a_4 is divisible by 33.
By the Little Theorem of Fermat, ak101(mod3)a_k^{10} \equiv 1 \pmod{3} unless ak0(mod3)a_k \equiv 0 \pmod{3}.
Therefore, if neither ak1a_{k-1} nor ak2a_{k-2} is divisible by 33, then
ak=ak110+ak2102(mod3). a_k = a_{k-1}^{10} + a_{k-2}^{10} \equiv 2 \pmod{3}.
By induction it follows now that an2(mod3)a_n \equiv 2 \pmod{3} for all n5n \ge 5.
Finally, using that any integer is congruent to its sum of digits modulo 33, we find that
m2014(2+0+1+4)20141(mod3) m \equiv 2014 \cdot (2 + 0 + 1 + 4) \equiv 2014 \equiv 1 \pmod{3}
and we conclude that manm \neq a_n for all n1n \ge 1.

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.