Difference between revisions of "2014 UNM-PNM Statewide High School Mathematics Contest II Problems/Problem 8"

(Solution)
(Solution)
 
Line 24: Line 24:
 
(660 cannot be withdrawn).
 
(660 cannot be withdrawn).
  
~mls
+
~yofro
  
 
== See also ==
 
== See also ==

Latest revision as of 10:51, 4 August 2020

Problem

A certain country uses bills of denominations equivalent to $\textdollar{15}$ and $\textdollar{44}$. 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 $\textdollar{x}$ if and only if you cannot withdraw $\textdollar{y}$, where x + y = $\textdollar{719}$.


Solution

As an example, consider the amount $15 * 44 = 660$. This is an amount that actually cannot be withdrawn. Otherwise, $15*44=15m+44n$ for some positive integers m and n which is a contradiction since then $15|44n$ (i.e., 15 divides 44n) and $44|15m$ hence $15|n$ and $44|m$, hence $15m+ 44n > 15 * 44$. On the other hand, the smallest amount we can withdraw is $15+44=59$. Notice that, $59 + 660 = 719$ so the claim is true in this particular case. In the next step, we show that any amount larger than $660$ can be withdrawn. For this, we use that $15$, $15 * 2$, $15 * 3,..., 15 * 44$ 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 $15m, m = 1, 2, . . . , 44$ 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 $x > 15 * 44 = 660$ we can find an integer m, $1 \le m \le 44$ such that $44|15m$. This shows that x can be written as $x = 15m + 44n$ for some positive integers m and n. We are left with case $59 < x < 660$. Suppose $x = 15m + 44n$ and $y = 719 - x = 15a + 44b$ for some positive integers m, n, a and b. Then we have $15(a+ m) + 44(b+n) = 719$ or $15(a+ m-1) + 44(b+n-1) = 660$ which is a contradiction with the fact that 660 cannot be written as a linear combination of 15 and 44 with positive integers (660 cannot be withdrawn).

~yofro

See also

2014 UNM-PNM Contest II (ProblemsAnswer KeyResources)
Preceded by
Problem 7
Followed by
Problem 9
1 2 3 4 5 6 7 8 9 10
All UNM-PNM Problems and Solutions
Invalid username
Login to AoPS