2014 UNM-PNM Statewide High School Mathematics Contest II Problems/Problem 8

Problem

A certain country uses bills of denominations equivalent to and . The ATM machines in this country can give at a single withdrawer any amount you request as long as both bills are used. Show that you can withdraw if and only if you cannot withdraw , where x + y = .

Solution

As an example, consider the amount . This is an amount that actually cannot be withdrawn. Otherwise, for some positive integers m and n which is a contradiction since then (i.e., 15 divides 44n) and hence and , hence . On the other hand, the smallest amount we can withdraw is . Notice that, so the claim is true in this particular case. In the next step, we show that any amount larger than can be withdrawn. For this, we use that , , is a complete set of residues mod 44. Indeed, clearly 44 cannot divide the difference of any two of them hence the remainders of the numbers when divided by 44 are different. On the other hand we have exactly 44 numbers so every remainder appears exactly once. Therefore, for any integer we can find an integer m, such that . This shows that x can be written as for some positive integers m and n. We are left with case . Suppose and for some positive integers m, n, a and b. Then we have or which is a contradiction with the fact that 660 cannot be written as a linear combination of 15 and 44 with positive imposters (660 cannot be withdrawn).

~yofro