Olympiad Maths Prep

Library / /5 of 6

Number theory Difficulty 7.4 National olympiad, round 2 Prove it Czech Republic

A strange calculator has only two buttons with positive integers, each consisting of two digits. It displays the number 11 at the beginning. Whenever a button with number NN is pressed, the calculator replaces the displayed number XX with the number XNX \cdot N or X+NX + N. Multiplication and addition alternate, multiplication is the first. (For example, if the number 1010 is on the 1st button, the number 2020 is on the 2nd button, and we consecutively press the 1st, 2nd, 1st, and 1st button, we get the results 110=101 \cdot 10 = 10, 10+20=3010 + 20 = 30, 3010=30030 \cdot 10 = 300, and 300+10=310300 + 10 = 310.) Decide whether there exist particular values of the two-digit numbers on the buttons such that one can display infinitely many numbers ending with
(a) 20152015,
(b) 58135813.

Solutions — 2

Solution 1

Let a,ba, b be the numbers written on the buttons. Consider the sequence (xn)n=0(x_n)_{n=0}^{\infty} such that xn+1x_{n+1} is formed by the last four digits of a(xn+b)a(x_n + b) for each n0n \ge 0, that is,
xn+1a(xn+b)(mod10000)and0xn+1<10000. x_{n+1} \equiv a(x_n + b) \pmod{10\,000} \quad \text{and} \quad 0 \le x_{n+1} < 10\,000.
Since there are only finitely many different possible values for xnx_n and each term is only dependent on the value of the previous term, the sequence must be periodic, with the period starting in the term whose value first occurs for the second time in the sequence.
In general, the period does not have to start with x0x_0 (e.g., if we take x0=1x_0 = 1, a=10a = 10, and b=10b = 10, then all the terms except x0x_0 end with zero, hence the value of x0x_0 never occurs again). However, consider the special case when aa is coprime with 1000010\,000. We claim that then the period starts with x0x_0. In fact, suppose that xnx_n is the first term of the sequence whose value occurs again, say xm=xnx_m = x_n, m>nm > n. If n>0n > 0, the equality can be rewritten as a(xn1+b)a(xm1+b)(mod10000)a(x_{n-1} + b) \equiv a(x_{m-1} + b) \pmod{10\,000}, that is,
10000a(xn1+b)a(xm1+b)=a(xn1xm1). 10\,000 \mid a(x_{n-1} + b) - a(x_{m-1} + b) = a(x_{n-1} - x_{m-1}).
Since aa is coprime with 1000010\,000, we have 10000xn1xm110\,000 \mid x_{n-1} - x_{m-1}, implying xn1=xm1x_{n-1} = x_{m-1}. But this is in contrary with the assumption xnx_n was the first term whose value repeats.
The previous paragraph suggests the algorithm how to display the requested number infinitely many times: We only need to produce the number once, using buttons with aa coprime with 1000010\,000, and then repeat the sequence +b,a,+b,a,+b, \cdot a, +b, \cdot a, \dots forever. In case we get the requested number with even number of presses, i.e., ending with addition, repeating the sequence a,+b,a,+b,\cdot a, +b, \cdot a, +b, \dots will do the same desired effect.
There are many ways how to display 20152015 using only few presses. E.g., we can try to find a,ba, b such that (1a+b)a=2015(1 \cdot a + b) \cdot a = 2015. Since 2015=513312015 = 5 \cdot 13 \cdot 31, we can take a=31a = 31 and b=513a=6531=34b = 5 \cdot 13 - a = 65 - 31 = 34. Indeed, we will get
13131+3465312015. 1 \xrightarrow{\cdot 31} 31 \xrightarrow{+34} 65 \xrightarrow{\cdot 31} 2015.
Notice that 3131 is coprime with 1000010\,000. Therefore the (a) part is solved.

In the part (b), we analogously wish to generate the sequence (xn)(x_n) described above with x0=5813x_0 = 5813. However, it is not so easy to produce the initial occurrence of 58135813 using only a few presses. Therefore, we shall instead produce 5813+b5813 + b, knowing that performing the sequence a,+b,a,\cdot a, +b, \cdot a, \dots afterwards will eventually reach 58135813. One possible way is to find a,ba, b according to the schema
1bb+b2ba2ab+a2ab+a=5813+b. 1 \xrightarrow{\cdot b} b \xrightarrow{+b} 2b \xrightarrow{\cdot a} 2ab \xrightarrow{+a} 2ab + a = 5813 + b.
The equation can be rewritten as (2a1)(2b+1)=11625=35331(2a-1)(2b+1) = 11625 = 3 \cdot 5^3 \cdot 31. From there, we can easily deduce several 2-digit solutions, one of which is a=47,b=62a = 47, b = 62. Since 4747 is coprime with 1000010\,000, the procedure
16262+62124475828+47587547+6247+62 1 \xrightarrow{\cdot 62} 62 \xrightarrow{+62} 124 \xrightarrow{\cdot 47} 5828 \xrightarrow{+47} 5875 \xrightarrow{\cdot 47} - \xrightarrow{+62} - \xrightarrow{\cdot 47} - \xrightarrow{+62} \dots
will reach numbers ending with 587562=58135875 - 62 = 5813 infinitely many times.

Solution 2

One can construct a sequence in which every 4-digit number occurs infinitely many times. Consider the calculator with a=11a = 11 and b=12b = 12. Applying the same arguments as above, we deduce that if we keep pressing the first button (with number 1111 on it, which is coprime with 1000010\,000), after a finite even number of presses we obtain a number ending with 00010001 again. If we change the button in the very last operation, that is, we replace +11+11 with +12+12, we get a number ending with 00020002. In the same way, we can always increment the number formed by the last 4 digits by 11 (or change 99999999 to 00000000). The conclusion follows.

Looking for a route rather than 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.