Maths Olympiad Prep

Library / /11 of 13

Number theory Difficulty 7.0 National olympiad Prove it Bulgaria

The positive integers a0,a1,,a9a_0, a_1, \dots, a_9 and b1,b2,,b9b_1, b_2, \dots, b_9 are such that a9<b9a_9 < b_9, akbka_k \neq b_k and 1k81 \le k \le 8. A cash machine is loaded with na9n \ge a_9 leva. For any 1i91 \le i \le 9 it is allowed to withdraw aia_i leva (if the machine has at least aia_i leva), and after that the bank puts in the machine bib_i leva. It is also allowed to withdraw a0a_0 without any action from the bank. Find all positive integers nn for which the cash machine can be emptied by the above described operations.

Solution

Set ds=asbsd_s = |a_s - b_s|, 0s90 \le s \le 9, where b0=0b_0 = 0. Without loss of generality assume that there exists kk, 0k80 \le k \le 8 such that asbs>0a_s - b_s > 0 for 0sk0 \le s \le k and asbs<0a_s - b_s < 0 for k+1s9k + 1 \le s \le 9.

If nn is one of the desired values then there exist positive integers x0,x1,,x9x_0, x_1, \dots, x_9 for which

()x0d0++xkdkxk+1dk+1x9d9=n. (\star) \qquad x_0d_0 + \dots + x_kd_k - x_{k+1}d_{k+1} - \dots - x_9d_9 = n.

Therefore d=GCD(d0,d1,,d9)d = \text{GCD}(d_0, d_1, \dots, d_9) is a divisor of nn.

We prove now that if dd is a divisor of nn then one can empty the cash machine.

Indeed, in this case it follows from Bezout's theorem that ()(\star) has solution (x0,x1,,x9)(x_0, x_1, \dots, x_9) in integers. Set D1=d0++dkD_1 = d_0 + \dots + d_k, D2=dk+1++d9D_2 = d_{k+1} + \dots + d_9, xs=xs+tD2x_s' = x_s + tD_2, 0sk0 \le s \le k, xs=xs+tD1x_s' = x_s + tD_1, k+1s9k+1 \le s \le 9. Since D1,D2>0D_1, D_2 > 0, it is clear that for big enough tt, (x0,,x9)(x_0', \dots, x_9') is a solution of ()(\star) in positive integers and x9>max(a8,,ak+1)x_9' > \max(a_8, \dots, a_{k+1}). Consider one such solution and let x0=x0+rD2x_0'' = x_0' + rD_2, xs=xsx_s'' = x_s', 1sk1 \le s \le k and xs=xs+rd0x_s'' = x_s' + rd_0, k+1s9k+1 \le s \le 9. For big enough rr we obtain a solution (x0,,x9)(x_0'', \dots, x_9'') of ()(\star), for which

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

()n+x9d9++xk+1dk+1>x1d1++xkdk. (\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 x9x_9'' times a9a_9 leva then x8x_8'' times a8a_8 leva, ..., xk+1x_{k+1}'' times ak+1a_{k+1} leva. After that we take x1x_1'' times a1a_1 leva, ..., xkx_k'' times aka_k leva. Since ()(\star\star) and ()(\star\star\star) all operations are feasible. Now ()(\star) implies that there are exactly x0d0x_0''d_0 leva left in the machine and we withdraw them by taking x0x_0'' times a0a_0 leva.

Answer. All na9n \ge a_9 divisible by dd.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.