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

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

Latest revision as of 21:04, 20 October 2022

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 imposters (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