Question 445464: What is the largest amount of postage that you CANNOT make using only stamps worth 5 cents and ll cents? You may use as many stamps as you wish, in any combination. Please go through all steps on how to get to the answer. Thank you
Answer by Edwin McCravy(20054)   (Show Source):
You can put this solution on YOUR website! What is the largest amount of postage that you CANNOT make using only stamps worth 5 cents and ll cents? You may use as many stamps as you wish, in any combination. Please go through all steps on how to get to the answer. Thank you
This is the Frobenius problem for two relatively
prime positive integers. In this case 5 and 11.
Frobenius theorem for 2 relatively prime positive integers
If p and q are two relatively prime positive integers greater
than 1, then the largest integer which cannot be expressed
as px+qy, where x and y are non-negative integers is given by
the formula pq-(p+q). That is, the difference between their
product and their sum.
So the product minus the sum of 5 and 11 is
5*11 - (5+11) = 55-16 = 39
So you can't get 39 cents worth of postage using only
5 and 11 cent stamps. However you can get any greater
amount of postage using only 5 and 11 cent stamps.
Edwin
|
|
|
