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?

Printable View

- Apr 11th 2005, 06:18 PMDantownPostage 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?

- Apr 11th 2005, 09:18 PMpaultwang
It is infinity.

- Apr 11th 2005, 09:41 PMCoolerActually no
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. - Apr 11th 2005, 09:41 PMMatrix
can you please explain?

- Apr 11th 2005, 09:42 PMMathManQuote:

Originally Posted by**Dantown**

- Apr 11th 2005, 09:45 PMpaultwang
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. - Apr 12th 2005, 08:15 AMDantownClarification
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. - Apr 12th 2005, 03:40 PMpaultwang
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.