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
See also
2014 UNM-PNM Contest II (Problems • Answer Key • Resources) | ||
Preceded by Problem 7 |
Followed by Problem 9 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 | ||
All UNM-PNM Problems and Solutions |