Going Postal

[plainglazed]

The annual debt of the United States Postal Service is projected to be $18 billion by the year 2015. To help stem this ever growing deficit, the USPS would like to increase the price it charges for a first class mailed letter from forty two to sixty three cents. A 50% increase amounting to all of $.21 to have a letter hand delivered, door to door, anywhere in the U.S. is terribly unpopular with the general public. Perhaps equally rational to these objections is the Post Office's most recent proposal to make the increase more acceptable. The concept is to charge a random amount in increments of whole cents between $.01 - $1.26 (inclusive). To save on printing costs it is expected that only five denominations of stamps would be offered and a maximum of five stamps per letter would be allowed. Can you suggest the five stamp amounts?

[Morningstar]

So the question is to find the five stamp amounts that can make any whole number of cents between $.01 and $1.26 inclusive using a maximum of five stamps?

Clearly, we need a 1 cent stamp, but can we go straight to 6 from there? (5x1+1)

[plainglazed]

one down, four more denominations to go...

[phil1882]

hmm

a rate of 3 seems too large;

1 3 9 27 81

to get a value of 80, requires two 27, two 9, two 3, two 1. which is too much.

a rate of 2 seems too small

1 3 7 15 31 cant get 126.

soo... how about a rate of e?

1 3 8 22 60

[plainglazed]

hey hey Phil - think that combo first falls short at $.43

[phil1882]

the best i personally can do...

is use the values 1,3,8,21,55. which allows all values between 1-88.

[plainglazed]

ahh, you can do better. no fibon.

[bonanova]

1 2 5 13 34

[phil1882]

yeah i think 89 is again not reachable with that squence.

[superprismatic]

1,4,9,31,51

[phil1882]

hey super. that seems close, but not quite. how would you get the number 25?

(9 9 4 1 1 1?)

though i think the idea is close.

[Thalia]

hey super. that seems close, but not quite. how would you get the number 25?

(9 9 4 1 1 1?)

though i think the idea is close.

4, 4, 4, 4, 9

[phil1882]

ah! thanks talia boy do i feel stupid! i'm still working through it, but i think super has the sequence.

i think in gereral however, you would want every other fib number for easy optimizing purposes.

[Rockmond]

Nice going Prismatic. Is there logic or math behind this solution or trial and error?

[superprismatic]

Nice going Prismatic. Is there logic or math behind this solution or trial and error?

I thought about it for a while, but I couldn't see an analytic solution to the problem.

So I just wrote a little program to solve it. By the way, there are no other solutions.

[plainglazed]

yes indeed, superprismatic. when i first composed this puzzle, did not know that it had been thoroughly investigated. and often with the same postage stamp theme. from what i can tell, a universal solution yet evades number theorists. dont have any programming skills to speak of myself so was limited to a spreadsheet. the highest i got was 115.

[Morningstar]

A possible extension: What is the highest maximum postal price for which this problem has a solution?

[PrimusPilum]

A possible extension: What is the highest maximum postal price for which this problem has a solution?

According to the premise

between $.01 - $1.26 (inclusive)

it seems to be $1.25

1 + 4 31s.

[Morningstar]

According to the premise

between $.01 - $1.26 (inclusive)

it seems to be $1.25

1 + 4 31s.

What I meant was that if you changed $1.26 to something higher, what is the highest value for which there is still a solution with 5 stamps?