Thread: Postage Stamps Problem

You have an unlimited supply of 5 cent stamps and 11 cent stamps. What is the greatest amount of exact postage you cannot make by using these stamps?

It is infinity.

Actually you could make infinity.

I beleive it is 39 cents.

It makes sense to me but I'm having a hard time demonstrating why.

can you please explain?

Originally Posted by Dantown

You have an unlimited supply of 5 cent stamps and 11 cent stamps. What is the greatest amount of exact postage you cannot make by using these stamps?

You cannot make or can make??

I see now..

If you have N, and keep decreasing N by 11. If N is large enough, eventually you will get a 0 or 5 in the ending digit. However, if N is just small enough, you cannot decrease N enough times to get to a 0 or 5 in the ending digit.

To Clarify . . .

The question is with an unlimited supply of 5 and 11 cent stamps what is the highest postage amount you cannot make exactly using a combination of stamps.

for example I cannot make 39 cents out of 5 and 11 cent stamps as Cooler suggests. But I could make 40, 41, 42 etc.

40 = 5+5+5+5+5+5+5+5
41 = 11+5+5+5+5+5+5
42 = 11+11+5+5+5+5

can anyone prove it?

I guess we have to start with P = 5*x + 11*y where x and y are integers.

For now we know 39 cents postage is the largest that you cannot make. You can prove that you can make any larger than 39. I can already think of:
40: by 5
41: minus 11, by 5
42: minus 22, by 5
43: minus 33, by 5
44: by 11
45: by 5
46: minus 11, by 5
47: minus 22, by 5
48: minus 33, by 5
49: minus 44, by 5

Any postage above 49 cents:
For any A: a positive integer > 4,
A*10+0: by 5
A*10+1: minus 11, then divisible by 5
A*10+2: minus 22, then divisible by 5
A*10+3: minus 33, then divisible by 5
A*10+4: minus 44, then divisible by 5
A*10+5: by 5
A*10+6: minus 11, then divisible by 5
A*10+7: minus 22, then divisible by 5
A*10+8: minus 33, then divisible by 5
A*10+9: minus 44, then divisible by 5


Postages greater than 44 are automatically covered because they can be subtracted by 0, 11, 22, 33, or 44, and will then be divisible by 5.