Czech-Polish-Slovak Mathematics Competition

Let $a,b$ be the numbers written on the buttons. Consider the sequence $(x_n{)}_{n=0}^{\infty }$ such that $x_{n+1}$ is formed by the last four digits of $a(x_n+b)$ for each $n\ge 0$, that is, $$x_{n+1}\equiv a(x_n+b)(\mathrm{mod}10000)\text{and}0\le x_{n+1}<10000.$$ Since there are only finitely many different possible values for $x_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 $x_0$ (e.g., if we take $x_0=1$, $a=10$, and $b=10$, then all the terms except $x_0$ end with zero, hence the value of $x_0$ never occurs again). However, consider the special case when $a$ is coprime with $10000$. We claim that then the period starts with $x_0$. In fact, suppose that $x_n$ is the first term of the sequence whose value occurs again, say $x_m=x_n$, $m>n$. If $n>0$, the equality can be rewritten as $a(x_{n-1}+b)\equiv a(x_{m-1}+b)(\mathrm{mod}10000)$, that is, $$10000\mid a(x_{n-1}+b)-a(x_{m-1}+b)=a(x_{n-1}-x_{m-1}).$$ Since $a$ is coprime with $10000$, we have $10000\mid x_{n-1}-x_{m-1}$, implying $x_{n-1}=x_{m-1}$. But this is in contrary with the assumption $x_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 $a$ coprime with $10000$, and then repeat the sequence $+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 $\cdot a,+b,\cdot a,+b,\dots$ will do the same desired effect. There are many ways how to display $2015$ using only few presses. E.g., we can try to find $a,b$ such that $(1\cdot a+b)\cdot a=2015$. Since $2015=5\cdot 13\cdot 31$, we can take $a=31$ and $b=5\cdot 13-a=65-31=34$. Indeed, we will get $$1\stackrel{\cdot 31}{\to }31\stackrel{+34}{\to }65\stackrel{\cdot 31}{\to }2015.$$ Notice that $31$ is coprime with $10000$. Therefore the (a) part is solved.

In the part (b), we analogously wish to generate the sequence $(x_n)$ described above with $x_0=5813$. However, it is not so easy to produce the initial occurrence of $5813$ using only a few presses. Therefore, we shall instead produce $5813+b$, knowing that performing the sequence $\cdot a,+b,\cdot a,\dots$ afterwards will eventually reach $5813$. One possible way is to find $a,b$ according to the schema $$1\stackrel{\cdot b}{\to }b\stackrel{+b}{\to }2b\stackrel{\cdot a}{\to }2ab\stackrel{+a}{\to }2ab+a=5813+b.$$ The equation can be rewritten as $(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=62$. Since $47$ is coprime with $10000$, the procedure $$1\stackrel{\cdot 62}{\to }62\stackrel{+62}{\to }124\stackrel{\cdot 47}{\to }5828\stackrel{+47}{\to }5875\stackrel{\cdot 47}{\to }-\stackrel{+62}{\to }-\stackrel{\cdot 47}{\to }-\stackrel{+62}{\to }\dots$$ will reach numbers ending with $5875-62=5813$ infinitely many times.

---

Alternative solution.

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