Difference between revisions of "2014 UNM-PNM Statewide High School Mathematics Contest II Problems/Problem 8"
(Created page with "== Problem == A certain country uses bills of denominations equivalent to <math>\textdollar{15}</math> and <math>\textdollar{44}</math>. The ATM machines in this country can giv...") |
(→Solution) |
||
(4 intermediate revisions by 3 users not shown) | |||
Line 8: | Line 8: | ||
== 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 integers | ||
+ | (660 cannot be withdrawn). | ||
+ | |||
+ | ~yofro | ||
== See also == | == See also == |
Latest revision as of 11:51, 4 August 2020
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 integers (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 |