Difference between revisions of "2014 UNM-PNM Statewide High School Mathematics Contest II Problems/Problem 8"
(Solution) |
Minediamonds (talk | contribs) m (→Solution) |
||
(3 intermediate revisions by 2 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 | 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 | withdrawn. Otherwise, <math>15*44=15m+44n</math> for some positive integers m and n which is a contradiction since then | ||
Line 22: | Line 21: | ||
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 | 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 | 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 | + | contradiction with the fact that 660 cannot be written as a linear combination of 15 and 44 with positive imposters |
(660 cannot be withdrawn). | (660 cannot be withdrawn). | ||
~yofro | ~yofro | ||
+ | |||
== See also == | == See also == | ||
{{UNM-PNM Math Contest box|year=2014|n=II|num-b=7|num-a=9}} | {{UNM-PNM Math Contest box|year=2014|n=II|num-b=7|num-a=9}} | ||
[[Category:Intermediate Algebra Problems]] | [[Category:Intermediate Algebra Problems]] |
Latest revision as of 21:04, 20 October 2022
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 |