Maths Olympiad Prep

Library / Belarus — Selection and Training Session /63 of 78

Belarus — Selection and Training Session

Algebra Difficulty 6.2 National Olympiad Prove it Belarus

In the sequence of digits 2,0,2,9,3,…2, 0, 2, 9, 3, \dots any digit is equal to the last digit in the decimal representation of the sum of four previous digits.

Do the four numbers 2,0,1,52, 0, 1, 5 in that order occur in the sequence? (Folklore)

Solution

In the given sequence consider all possible quadruple of successive digits. There are finite number of possible quadruples (no more than 10410^4). So if we proceed the sequence sufficiently long, some of the quadruple will occur more than once:
2029…d c b a…d1 c1 b1 a1… 2029 \dots d\ c\ b\ a \dots d_1\ c_1\ b_1\ a_1 \dots
(here d=d1d = d_1, c=c1c = c_1, b=b1b = b_1, a=a1a = a_1). Note that any quadruple uniquely defines the preceding digits. That is, if ee and e1e_1 precede to d c b ad\ c\ b\ a and d1 c1 b1 a1d_1\ c_1\ b_1\ a_1, respectively, then e=e1e = e_1:
2029…e d c b a…e1 d1 c1 b1 a1… 2029 \dots e\ d\ c\ b\ a \dots e_1\ d_1\ c_1\ b_1\ a_1 \dots
Hence the quadruple 20292029 should occur in the given sequence somewhere between d c b ad\ c\ b\ a and d1 c1 b1 a1d_1\ c_1\ b_1\ a_1:
2029…d c b a…2029…d1 c1 b1 a1… 2029 \dots d\ c\ b\ a \dots 2029 \dots d_1\ c_1\ b_1\ a_1 \dots
Now proceeding to the left we can easily see which digits precede the second quadruple 20292029:
2029…d c b a…2015 84 85 52 029 d1 c1 b1 a1… 2029 \dots d\ c\ b\ a \dots 2015\ 84\ 85\ 52\ 029\ d_1\ c_1\ b_1\ a_1 \dots
We see that the quadruple 20152015 occurs in the sequence.

Remark. Considering the given sequence modulo 22 we see that it is periodic with 55 as a period. Further, considering the sequence modulo 55, starting from 20242024 (≡2029(mod5)\equiv 2029 \pmod{5}) after 7878 moves (it takes about ten minutes) we can get 10121012 which are 3⋅2,3⋅0,3⋅2,3⋅43 \cdot 2, 3 \cdot 0, 3 \cdot 2, 3 \cdot 4 modulo 55. So after 4⋅784 \cdot 78 moves we get 34⋅2,34⋅0,32,34⋅43^4 \cdot 2, 3^4 \cdot 0, 3^2, 3^4 \cdot 4 which is the starting quadruple 20242024. Thus we conclude that the sequence modulo 55 has period 4⋅78=3124 \cdot 78 = 312. So the initial sequence is periodic with period 5⋅312=15605 \cdot 312 = 1560. So to get the quadruple 20152015 in the sequence we need to perform 1560−9=15511560 - 9 = 1551 moves.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.