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

Monday, September 6th, 2010

### 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:

1. 5,882,350 stamps of 17 cent denomination
2. 1 stamp of 9 cent denomination
3. 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:

1. We have defined q=17x+9y+5z
2. We know that q-1=17(x)+9(y+1)+5(z-2)