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) \qquad x_0d_0 + \dots + x_kd_k - x_{k+1}d_{k+1} - \dots - x_9d_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 + \dots + d_k$, $D_2 = d_{k+1} + \dots + d_9$, $x_s' = x_s + tD_2$, $0 \le s \le k$, $x_s' = x_s + tD_1$, $k+1 \le s \le 9$. Since $D_1, D_2 > 0$, it is clear that for big enough $t$, $(x_0', \dots, x_9')$ is a solution of $(\star)$ in positive integers and $x_9' > \max(a_8, \dots, a_{k+1})$. Consider one such solution and let $x_0'' = x_0' + rD_2$, $x_s'' = x_s'$, $1 \le s \le k$ and $x_s'' = x_s' + rd_0$, $k+1 \le s \le 9$. For big enough $r$ we obtain a solution $(x_0'', \dots, x_9'')$ of $(\star)$, for which

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

$$(\star\star\star) \qquad n + x_9''d_9 + \dots + x_{k+1}''d_{k+1} > x_1''d_1 + \dots + x_k''d_k.$$

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

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