Question 446755: 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. Also please solve it with mathematical induction.
Answer by richard1234(7193)   (Show Source):
You can put this solution on YOUR website! We wish to find the largest number that cannot be expressed in the form C = 5x + 11y, where x and y are nonnegative integers. If we fix various x- or y-values, we can create different arithmetic sequences and quickly determine which integers can or cannot be made. We will fix y-values first, because there are fewer indices modulo 5:
y = 0 --> 0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55,... 5y
y = 1 --> 11, 16, 21, 26, 31, 36, 41, 46, 51, 56,... 5y + 11
y = 2 --> 22, 27, 32, 37, 42, 47, 52, 57, ...5y + 22
y = 3 --> 33, 38, 43, 48, 53, 58, ...5y + 33
y = 4 --> 44, 49, 54, 59, ...5y + 44
We do not need to do y = 5 because all numbers that satisfy y = 5 also satisfy y = 0 (e.g. use five fewer 11-cent stamps, and use 11 more five-cent stamps).
We can check that 39 is the smallest number that cannot be obtained. We can prove it by looking at each index (0, 1, ..., 4) and noting that for y = 1, 6 is the largest positive number congruent to 1 mod 5 that is not possible to make; 17 is the largest positive number congruent to 2 mod 5 that is not possible to make, etc. 39 is the largest of these "impossible" numbers.
However, proving via induction is a little tricker since a base case is more difficult to establish. We could say that since 40, 41, ..., 44 are all obtainable, then we can induct by adding a multiple of 5 (i.e. if k is possible, so is k+5), and since we have covered all indices mod 5, all amounts greater than 40 cents can be formed.
|
|
|
