41st Balkan Mathematical Olympiad

Let $f(n)={\sum }_{k=1}^{\lfloor \frac{n}{3}\rfloor }\left(\genfrac{}{}{0ex}{}{n}{3k}\right)8^k$ and $\omega \ne 1$ be a third root of the unity. Using the fact that for every integer $k\ge 0$: $$1+{\omega }^k+{\omega }^{2k}=\{\begin{array}{ll}3,& \text{if }3\mid k\\ 0,& \text{otherwise,}\end{array}$$ we get that: $$\begin{array}{rl}f(n)+1& =\sum _{k=0}^{\lfloor \frac{n}{3}\rfloor }\left(\genfrac{}{}{0ex}{}{n}{3k}\right)2^k=\frac{1}{3}\sum _{k=0}^n(1+{\omega }^k+{\omega }^{2k})\left(\genfrac{}{}{0ex}{}{n}{k}\right)2^k\\ & =\frac{1}{3}{3}^n+\frac{1}{3}(1+2\omega {)}^n+\frac{1}{3}(1+2{\omega }^2{)}^n.\end{array}$$ Now note that $3,1+2\omega$ and $1+2{\omega }^2$ are the roots of the polynomial: $$P(x)=(x-3)(x-1-2\omega )(x-1-2{\omega }^2)=(x-1{)}^3-8=x^3-3x^2+3x-9$$ which, in turn, is the characteristic polynomial of the recursive sequence $(a_i{)}_{i\ge 0}$: $$a_{i+3}=3a_{i+2}-3a_{i+1}+9a_i\text{ for }i\ge 0.$$ Thus, if we set $a_i=f(i)+1=1$ for $0\le i\le 2$, then $f(n)+1=a_n$ for every $n\ge 0$. Let $b_i=a_i(\mathrm{mod}10^{2023})$. Since $\text{gcd}(3,10^{2023})=1$, any three consecutive terms of the sequence $(b_i{)}_{i\ge 0}$ uniquely determine the previous as well as the next term of this sequence. Together with the fact that there are only finitely many residues modulo $10^{2023}$, we conclude that the sequence $(b_i{)}_{i\ge 0}$ is periodic with some period $d>3$ (since $b_3=a_3=9$). Therefore: $$9(f(d-1)+1)=9a_{d-1}=a_{d+2}-3a_{d+1}+3a_d\equiv a_2-3a_1+3a_0(\mathrm{mod}10^{2023})=1(\mathrm{mod}10^{2023}).$$ Finally, since $9\mid 8.10^{2023}+1$, we conclude that $9^{\frac{8.10^{2023}+1}{9}}\equiv 1(\mathrm{mod}10^{2023})$ and consequently: $$f(d-1)+1=a_{d-1}\equiv \frac{8.10^{2023}+1}{9}=\underset{2022}{\underbrace{88\dots 89}}(\mathrm{mod}10^{2023})$$

and thus $f(d-1)\equiv \underset{2022}{\underbrace{88\dots 8}}(\text{mod }10^{2023})$. Therefore $n=d-1$ has the desired property. $\square$