# What is the Largest Amount of Postage That Cannot be Made Using These Stamp Denominations: 17 Cents, 9 Cents & 5 Cents?

### Solution:

We’re not sure we understand the question, because if you have enough stamps (of any denomination) you can cross any amount. However, you said that the total value (let’s call is “q”) has to be less than a million dollars (e.g. $999,999.99), so let’s work backwards. $999,999.99 can be obtained as follows:

- 5,882,350 stamps of 17 cent denomination
- 1 stamp of 9 cent denomination
- 8 stamps of 5 cent denomination

So we have shown the largest amount of postage that can be paid (below the million dollar limit) is $999,999.99.

Now let’s assume that the amount paid has to be exact, i.e. we cannot overpay. This is a lot more complicated, as to do this we have to consider all values of q, where q = 17x + 9y + 5z, and where x, y and z are positive integers. We could write a computer program to check the value of q for all values of x, y and z, and then see which values are missing, and finally pick the highest number among the missing values. We might want to work backwards from $999,999.99 (since we know we can reach $999,999.99) and check to see if the a small amount is possible. For example, we know that we can remove one of the 8 stamps of 5 cent denomination, so that gets us to $999,999.94. We could remove another 5 cent stamp to get to $999,999.89, and then add a 9 cent stamp to get to $999,999.98 (x= 5,882,352; y=2; z=6). We can continue this exercise until we hit a number that we cannot create with any combination of values for x, z and z.

The easiest way to solve the problem is to recognize to work backwards to prove that we can calculate most values of q below $1,000,000:

- We have defined q=17x+9y+5z
- We know that q-1=17(x)+9(y+1)+5(z-2)
- So let’s start with (x=0; y=0, z=20,000,000), whereby q=$1,000,000
- Now increase y by 1 and decrease z by 2: q=9,999,999.99
- Again increase y by 1 and decrease z by 2: q=9,999,999.98
- Continue this until z reaches zero (x=0; y=10,000,000; z=0), where q=$900,000
- Start again with (x=0;y=0;z=18,000,000), where q=$900,000
- Repeat the process of decreasing 1 y by one and decreasing z by 2 (you can do this in an Excel spreadsheet)
- Continue until z reaches zero, and then reset y to zero and z to whatever is required to reach the last value of q (or a number slightly higher)
- Repeat the exercise until you reach a value of q = 32 cents.
- Now you need the 17 cent stamp to get to q=31 (x=1,y=1,z=1).
- You will also need the 17 cent stamp for q=26 and q=22 (see blow)
- You can find solutions for q down to 22, but you will get stuck on the number 21…so that must be the answer!

Posted in 12th Grade, Homework Answers, Math Answers | No Comments »