XXXI Brazilian Math Olympiad

We will choose two large positive integers $r$, $s$, and take $m=r+s$, $a_j=1$ for $1\le j\le r$ and $a_j=2$ for $r+1\le j\le r+s=m$. We have $q_{k+1}=q_k+q_{k-1}$, for $1\le k\le r-1$, and so $q_j=F_{j+1}$, for $0\le j\le r$, where $$F_j=\frac{1}{\sqrt{5}}\left({\left(\frac{1+\sqrt{5}}{2}\right)}^j-{\left(\frac{1-\sqrt{5}}{2}\right)}^j\right)=\frac{1+o(1)}{\sqrt{5}}{\left(\frac{1+\sqrt{5}}{2}\right)}^j$$ is the $j$-th term of Fibonacci's sequence, for $j\ge 1$. So $q_j=\frac{1+o(1)}{\sqrt{5}}(\frac{1+\sqrt{5}}{2}{)}^{j+1}$ for large $j$.

On the other hand, we have $q_{k+1}=2q_k+q_{k-1}$ for $r\le k\le m-1$, and so $q_{r+j}=u_{j+1}{q}_r+u_j{q}_{r-1}$, where $(u_j{)}_{j\ge 0}$ is the sequence given by $u_0=0$, $u_1=1$ and $u_{k+2}=2u_{k+1}+u_k$, for $k\ge 0$. Since $$u_k=\frac{1}{2\sqrt{2}}((1+\sqrt{2}{)}^k-(1-\sqrt{2}{)}^k)=\frac{1+o(1)}{2\sqrt{2}}(1+\sqrt{2}{)}^k,\text{for }k\ge 0,$$ we get $$\begin{array}{rl}{q}_{r+j}& =\frac{1+o(1)}{2\sqrt{2}}((1+\sqrt{2})q_r+q_{r-1})(1+\sqrt{2}{)}^j\\ & =\frac{1+o(1)}{2\sqrt{10}}\left(1+\sqrt{2}+\frac{\sqrt{5}-1}{2}\right)(1+\sqrt{2}{)}^j{\left(\frac{1+\sqrt{5}}{2}\right)}^{r+1}\\ & =(1+o(1))\frac{4+\sqrt{10}+\sqrt{2}}{8\sqrt{5}}(1+\sqrt{2}{)}^j{\left(\frac{1+\sqrt{5}}{2}\right)}^{r+1},\end{array}$$ provided that $j$ and $r$ are large.

Since $\log (1+\sqrt{2})/\log (\frac{1+\sqrt{5}}{2})$ is irrational, the result follows (by taking logarithms) from the elementary fact below: Given $\alpha$, $\beta >0$ such that $\alpha /\beta$ is irrational, $ϵ>0$ and $r>0$, there is $x_0>0$ such that, for every $x\in \mathbb{R}$, $x\ge x_0$, there are positive integers $m$, $n\ge r$ such that $|m\alpha +n\beta -x|<ϵ$.