Maths Olympiad Prep

Library / /25 of 35

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:
2029d c b ad1 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:
2029e d c b ae1 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:
2029d c b a2029d1 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:
2029d c b a2015 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 32,30,32,343 \cdot 2, 3 \cdot 0, 3 \cdot 2, 3 \cdot 4 modulo 55. So after 4784 \cdot 78 moves we get 342,340,32,3443^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 478=3124 \cdot 78 = 312. So the initial sequence is periodic with period 5312=15605 \cdot 312 = 1560. So to get the quadruple 20152015 in the sequence we need to perform 15609=15511560 - 9 = 1551 moves.

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.