SOLUTION: 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 throu

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.
RELATED QUESTIONS
What is the largest amount of postage that you CANNOT make using only stamps worth 5... (answered by Edwin McCravy)

SUPPOSE THAT YOU HAVE AN UNLIMITED SUPPLY OF 5 CENT STAMPS AND 11 CENT STAMPS. YOU CAN... (answered by bucky)

Larry has 4-cent stamps and 9-cent stamps, which he can combine to produce various... (answered by stanbon)

If the post office only has stamps of the denominatations 5 and 7 cents, what amount of... (answered by richard1234)

assuming you had a unlimited supply of 3cent and 7cent stamps what is the largest amount... (answered by ikleyn)

Nigel has a stack of 4 pence stamps and 5 pence stamps. What is the largest number of... (answered by CubeyThePenguin)

Bertha has 35 postage stamps. Some are valued at the old postage rate of 55cents and some (answered by rwm)

The instructions are to: "Use mathematical induction to show that any postage of at lease (answered by solver91311)

You have 100 stamps that have a total value of $31.02. Some of the stamps are worth 24... (answered by Cromlix)