62nd Czech and Slovak Mathematical Olympiad

Cutting off the last digit of a satisfactory $(n+1)$-digit integer yields a satisfactory $n$-digit integer. Notice how a satisfactory $(n+1)$-digit integer can be constructed from a satisfactory $n$-digit integer. If the last digit of the integer is $1$, we can append any of the digits $3$, $4$, $5$. If the last digit is $2$, we can append $4$ or $5$; if it is $3$, $1$ or $5$ can be appended; if it is $4$, $1$ or $2$ can be appended; and, finally, in the case of $5$, we can append any of the digits $1$, $2$, $3$. Thus we can see that only the last digit matters. So now, let $a_n$ denote the number of satisfactory $n$-digit integers ending in $1$ or $5$; similarly $b_n$ for $2$ or $4$, and $c_n$ for integers ending in $3$. Then $p(n)=a_n+b_n+c_n$. Apparently, $a_1=b_1=2$, $c_1=1$, $p(1)=5=5\cdot 2.4^0=5\cdot 2.5^0$, $a_2=6$, $b_2=4$, $c_2=2$, $p(2)=12=5\cdot 2.4^1<5\cdot 2.5^1$. The above reasoning implies the recurrent formulae $$a_{n+1}=a_n+b_n+2c_n,b_{n+1}=a_n+b_n,c_{n+1}=a_n.(1)$$ Hence it follows that $a_3=14$, $b_3=10$, $c_3=6$, $p(3)=30\in (5\cdot 2.4^2;5\cdot 2.5^2)$. Using mathematical induction, we prove that for every $n\ge 3$, it holds that $$a_n\ge 2.4^n,b_n\ge \frac{2}{3}\cdot 2.4^n,c_n\ge 2.4^{n-1}.$$ It indeed does for $n=3$. If $a_n\ge 2.4^n$, $b_n\ge \frac{2}{3}\cdot 2.4^n$ and $c_n\ge 2.4^{n-1}$, then also $$\begin{array}{rl}{a}_{n+1}& =a_n+b_n+2c_n\ge 2.4^n+\frac{2}{3}\cdot 2.4^n+2\cdot 2.4^{n-1}=\\ & =2.4^n\cdot \left(1+\frac{2}{3}+\frac{5}{6}\right)=2.5\cdot 2.4^n>2.4^{n+1},\\ b_{n+1}& =a_n+b_n\ge 2.4^n+\frac{2}{3}\cdot 2.4^n=\frac{5}{3}\cdot 2.4^n>\frac{2}{3}\cdot 2.4^{n+1},\\ c_{n+1}& =a_n\ge 2.4^n.\end{array}$$ It follows from the proved inequalities that $$p(n)=a_n+b_n+c_n\ge 2.4^n+\frac{2}{3}\cdot 2.4^n+2\cdot 2.4^{n-1}=(2.4+1.6+1)\cdot 2.4^{n-1}=5\cdot 2.4^{n-1}.$$

The latter inequality can be proved analogously; we will verify that for $n\ge 3$, $$a_n\le k\cdot 2.5^n,b_n\le k\cdot \frac{2}{3}\cdot 2.5^n,c_n\le k\cdot 2.5^{n-1},(2)$$ where $k$ is a suitably chosen number. Then we will have $$p(n)=a_n+b_n+c_n\le k\cdot 2.5^{n-1}\cdot \left(2.5+\frac{5}{3}+1\right)=k\cdot 2.5^{n-1}\cdot \frac{31}{6}=5k\cdot \frac{31}{30}\cdot 2.5^{n-1}.$$ Therefore, setting $k=\frac{30}{31}$, we get $p(n)\le 5\cdot 2.5^{n-1}$ for every $n\ge 3$. It remains to prove, by mathematical induction, the inequalities (2) where $k=\frac{30}{31}$. They hold for $n=3$. If (2) holds, we also have $$\begin{array}{rl}{a}_{n+1}& =a_n+b_n+2c_n\le k\cdot 2.5^n\cdot \left(1+\frac{2}{3}+\frac{4}{5}\right)=k\cdot 2.5^n\cdot \frac{37}{15}<k\cdot 2.5^{n+1},\\ b_{n+1}& =a_n+b_n\le k\cdot 2.5^n\cdot \left(1+\frac{2}{3}\right)=k\cdot \frac{2}{3}\cdot 2.5^{n+1},\\ c_{n+1}& =a_n\le k\cdot 2.5^n.\end{array}$$

---

Alternative solution.

We will show that each of the sequences $\{a_n\}$, $\{b_n\}$, $\{c_n\}$ defined in the above solution satisfies (as a consequence of the equalities (1)) the recurrent equation $x_{n+2}=2x_{n+1}+2x_n-2x_{n-1}$, and so this equation is satisfied by the sequence $p(n)=a_n+b_n+c_n$ in question, which we will denote by (3). Indeed, the first and third equalities of (1) give $a_{n+1}=a_n+b_n+2a_{n-1}$, whence $$b_n=a_{n+1}-a_n-2a_{n-1},\text{so}{b}_{n+1}=a_{n+2}-a_{n+1}-2a_n.$$ Considering the second equality in (1), we thus get $$a_{n+2}-a_{n+1}-2a_n=b_{n+1}=a_n+b_n=a_n+(a_{n+1}-a_n-2a_{n-1}).$$ Confronting the marginal expressions leads to the mentioned equality $$a_{n+2}=2a_{n+1}+2a_n-2a_{n-1}.$$ Triple substitution of $a_n=b_{n+1}-b_n$ into the equality $b_n=a_{n+1}-a_n-2a_{n-1}$ yields $$b_n=(b_{n+2}-b_{n+1})-(b_{n+1}-b_n)-2(b_n-b_{n-1}),$$ which can be rearranged to $$b_{n+2}=2b_{n+1}+2b_n-2b_{n-1}.$$ Finally, the sequence $\{c_n\}$ is merely a shifted sequence $\{a_n\}$, so $$c_{n+2}=a_{n+1}=2a_n+2a_{n-1}-2a_{n-2}=2c_{n+1}+2c_n-2c_{n-1}.$$ Combining all of the three recurrent formulae, we get $$p(n+2)=2p(n+1)+2p(n)-2p(n-1).(3)$$

Using mathematical induction, we will prove that for every $k\ge 1$, $$2.4p(k)\le p(k+1)\le 2.5p(k).(4)$$ The inequalities (4) hold for both $k=1$ and $k=2$. If (4) holds for all $k\in \{1,2,\dots ,n+1,n+2\}$, then $$\begin{array}{rl}p(n+3)& =2(p(n+2)+p(n+1)-p(n))\ge 2\left(p(n+2)+p(n+1)-\frac{p(n+1)}{2.4}\right)=2\left(p(n+2)+\frac{7p(n+1)}{12}\right)\ge 2\left(p(n+2)+\frac{7}{12}\cdot \frac{p(n+2)}{2.5}\right)=\frac{74p(n+2)}{30}>2.4p(n+2).\end{array}$$ Similarly, $$\begin{array}{rl}p(n+3)& \le 2\left(p(n+2)+p(n+1)-\frac{p(n+1)}{2.5}\right)\le 2\left(p(n+2)+\frac{3}{5}\cdot \frac{p(n+2)}{2.4}\right)=2.5p(n+2).\end{array}$$ The equalities $5\cdot 2.4^0=p(1)=5\cdot 2.5^0$ and the inequalities of (4) imply that the inequality $5\cdot 2.4^{n-1}\le p(n)\le 5\cdot 2.5^{n-1}$ holds for every positive integer $n$.