Bulgarian National Mathematical Olympiad

Set $d_s=|a_s-b_s|$, $0\le s\le 9$, where $b_0=0$. Without loss of generality assume that there exists $k$, $0\le k\le 8$ such that $a_s-b_s>0$ for $0\le s\le k$ and $a_s-b_s<0$ for $k+1\le s\le 9$.

If $n$ is one of the desired values then there exist positive integers $x_0,x_1,\dots ,x_9$ for which

$$(\star )x_0{d}_0+\cdots +x_k{d}_k-x_{k+1}{d}_{k+1}-\cdots -x_9{d}_9=n.$$

Therefore $d=\text{GCD}(d_0,d_1,\dots ,d_9)$ is a divisor of $n$.

We prove now that if $d$ is a divisor of $n$ then one can empty the cash machine.

Indeed, in this case it follows from Bezout's theorem that $(\star )$ has solution $(x_0,x_1,\dots ,x_9)$ in integers. Set $D_1=d_0+\cdots +d_k$, $D_2=d_{k+1}+\cdots +d_9$, $x_s^{\prime }=x_s+t{D}_2$, $0\le s\le k$, $x_s^{\prime }=x_s+t{D}_1$, $k+1\le s\le 9$. Since $D_1,D_2>0$, it is clear that for big enough $t$, $(x_0^{\prime },\dots ,x_9^{\prime })$ is a solution of $(\star )$ in positive integers and $x_9^{\prime }>\max (a_8,\dots ,a_{k+1})$. Consider one such solution and let $x_0^{\prime \prime }=x_0^{\prime }+r{D}_2$, $x_s^{\prime \prime }=x_s^{\prime }$, $1\le s\le k$ and $x_s^{\prime \prime }=x_s^{\prime }+r{d}_0$, $k+1\le s\le 9$. For big enough $r$ we obtain a solution $(x_0^{\prime \prime },\dots ,x_9^{\prime \prime })$ of $(\star )$, for which

$$(\star \star )x_9^{\prime \prime }\ge \max (a_8,\dots ,a_{k+1})$$

$$(\star \star \star )n+x_9^{\prime \prime }{d}_9+\cdots +x_{k+1}^{\prime \prime }{d}_{k+1}>x_1^{\prime \prime }{d}_1+\cdots +x_k^{\prime \prime }{d}_k.$$

We draw money in the following way. Take first $x_9^{\prime \prime }$ times $a_9$ leva then $x_8^{\prime \prime }$ times $a_8$ leva, ..., $x_{k+1}^{\prime \prime }$ times $a_{k+1}$ leva. After that we take $x_1^{\prime \prime }$ times $a_1$ leva, ..., $x_k^{\prime \prime }$ times $a_k$ leva. Since $(\star \star )$ and $(\star \star \star )$ all operations are feasible. Now $(\star )$ implies that there are exactly $x_0^{\prime \prime }{d}_0$ leva left in the machine and we withdraw them by taking $x_0^{\prime \prime }$ times $a_0$ leva.

Answer. All $n\ge a_9$ divisible by $d$.